HDU1232畅通工程

http://acm.split.hdu.edu.cn/showproblem.php?pid=1232

HDU1232畅通工程

 ///
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=;
int fa[M];
int fin(int x){
return fa[x]==x?fa[x]:fa[x]=fin(fa[x]);
}
int unin(int x,int y){
return fa[fin(y)]=fin(x);
}
int main(){
int m,n;
while(cin>>m>>n&&m){
memset(fa,,sizeof(fa));
for(int i=;i<m;i++){
fa[i]=i;
}
int a,b;
for(int i=;i<n;i++){
scanf("%d%d",&a,&b);
unin(a,b);
}
int temp=;
for(int i=;i<m;i++){
if(fa[i]==i){
temp++;
}
}
cout<<temp-<<endl;///在最后输出的是temp-1的原因是,temp的构成是树的根点
///是fa[i]=i+其余的点是未被连接进并查集的点
}
}
上一篇:(转)EasyUI 分页总结


下一篇:2.python基础深入(元组、字符串、列表、字典)