算法学习 之 并查集

leecode 中这题就需要并查集
代码如下

typedef struct{int * parents;int * sizes;} UnionFind;// 下面建立一个初始化UnionFind * NewUnionFind(int n){UnionFind * uf = (UnionFind *) malloc(sizeof(UnionFind));uf->parents = (int *) malloc (sizeof(int)*n);uf->sizes = (int *) malloc (sizeof(int)*n);// 初始化for(int i = 0; i parents[i] = i;uf->sizes[i] = 1;}return uf;}// 清空void FreeUnionFind(UnionFind * uf){free(uf->parents);free(uf->sizes);free(uf);}int Find(UnionFind * uf,int x){if(uf->parents[x] == x){return x;}return uf->parents[x] = Find(uf , uf->parents[x]);}// 合并void Union(UnionFind * uf , int x , int y){int rx = Find(uf,x) , ry = Find(uf,y);if(rx != ry){if(uf->sizes[rx] > uf->sizes[ry]){uf->parents[ry] = rx;uf->sizes[rx] += uf->sizes[ry];}else{uf->parents[rx] = ry;uf->sizes[ry] += uf->sizes[rx];}}}int getSize(UnionFind * uf,int x){return uf->sizes[x];}long long countPairs(int n, int** edges, int edgesSize, int* edgesColSize){UnionFind * uf = NewUnionFind(n);for(int i = 0 ; i< edgesSize ;i ++){Union(uf,edges[i][0],edges[i][1]);}long long res = 0;for(int i = 0 ; i < n ; i++){res += n - getSize(uf , Find(uf,i));}FreeUnionFind(uf);return res/2;}