解题思路:
比并查集慢。寻找连通树的数量。
参考代码:
#include<bits/stdc++.h> using namespace std; const int mapSize = 1011; bool Map[mapSize][mapSize]; bool Vis[mapSize]; int point; int prims(){ int counts = 0; queue<int> poi; for(int i = 1; i <= point; i++){ if(!Vis[i]){ Vis[i] = true; poi.push(i); while(!poi.empty()){ int now = poi.front(); for(int pos = 1; pos <= point; pos++) if(!Vis[pos] && Map[now][pos]){ Vis[pos] = true; poi.push(pos); } poi.pop(); } counts++; i = 1; } } return counts; } int main(){ int paths, pos1, pos2; while(cin >> point >> paths){ while(paths--){ cin >> pos1 >> pos2; if(!pos1) return 0; Map[pos1][pos2] = true; Map[pos2][pos1] = true; } cout << prims() - 1 << endl; memset(Vis, false, sizeof(Vis)); memset(Map, false, sizeof(Map)); } }
0.0分
9 人评分
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:601 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:481 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:583 |
C语言训练-大、小写问题 (C语言代码)浏览:2349 |
简单的a+b (C语言代码)浏览:667 |
【排队买票】 (C语言代码)浏览:899 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:1242 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:349 |
敲七 (C++代码)浏览:1051 |
C语言训练-8除不尽的数 (C语言代码)浏览:1396 |