###并查集
假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友...),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。 假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。
int uset[10001];
int find(int x){
if (x != uset[x]){
//路径压缩
uset[x] = find(uset[x]);
}
return uset[x];
}
void unionSet(int x , int y){
int t = find(x);
int h = find(y);
if(t < h)
set[h] = t;
else
set[t] = h;
}
int friends(int n , int m , int* r[]){
int i , count;
for(i = 1 ; i <= n ; ++i)
uset[i] = i;
for(i = 0 ; i < m ; ++i)
unionSet(r[i][0] , r[i][1]);
count = 0;
for(i = 1 ; i <= n ; ++i){
if(uset[i] == i)
++count;
}
return count;
}