并查集

uset.md

###并查集

假如已知有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;
    }