畅通工程 （C++代码）并查集

解题思路:        留个笔记

           此题相当于寻找有多少连通块，如果只有一个，说明全部连通，不需要修路，

           如果有两个连通块，则只需随意在他们之间修条路即可连通。

        答案即为搜出连通块数量-1

        并查集则正是处理此类题的一种常用方法。

注意事项:
        
参考代码:

#include <iostream>
#include <cstring>
using namespace std;
int arr[1050];
bool vis[1000];
int root(int x){	//寻找根节点 
	int r=x;
	while(r!=arr[r]){	
		r=arr[r];
	}
	int i=x,j;
	while(i!=arr[r]){	//把所有子节点指向新的父亲 
		j=arr[r];
		arr[i]=r;
		i=j;
	}
}
void deal(int a,int b){//处理数据 
	int fx=root(a);
	int fy=root(b);
	if(fx!=fy){
		arr[fx]=fy;
	}
}
int main(){
	int n,m;
	while(cin>>n>>m&&n!=0){
		memset(vis,0,sizeof(vis)); //初始化 
		memset(arr,0,sizeof(arr));
		for(int i=1;i<=n;i++)	
			arr[i]=i;
		while(m--){
			int a,b;
			cin>>a>>b;
			deal(a,b);
		}
		int ans=0;
		for(int i=1;i<=n;i++)    //标记连通
			vis[root(i)]=1;
		for(int i=1;i<=n;i++)
			if(vis[i])
				ans++;
		cout<<ans-1<<endl;
	}
	
	return 0;
}