算法学习 之 并查集

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 < n ;i++){
        uf->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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58