畅通工程 （C++代码）（连通树）

解题思路:

    比并查集慢。寻找连通树的数量。

参考代码:

#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));
	}
}