并查集（也称不相交集--disjoint set）

并查集（也称不相交集–disjoint set）

并查集广泛应用于图和树一些基本操作，如给定一个网络的连接，{ connections = [[0,1],[0,2],[1,2]] }可以判定网络中每台计算机是否可以相接（即森林中有几棵树）。
本文第一部分用【数组】实现并查集，并配合一道leecode题来进行应用。第二部分为优化的并查集，同时配合一道leetcode来检验
1.用数组来实现并查集。数组中有两种节点：值为 -1，即为数组（有可能是一个节点）；值为正值，该值即为父节点的index。

题目请参考leetcode 1319 题：
1319. 连通网络的操作次数
1
2

void ds_init(int *data,int length){
    int i=0;
    for(i=0;i<length;i++){
        data[i]=-1;
    }
}

int ds_find(int *data,int length,int num){
    if(data[num]==-1)
        return num;
    else{
        int temp=num;
        while(data[temp]!=-1){
            temp=data[temp];
        }
        return temp;
    }
}

void ds_union(int *data,int length,int first,int second){
    int p1=ds_find(data,length,first);
    int p2=ds_find(data,length,second);
    if(p1==p2)
        return;
    data[p2]=p1;
    return;
}


//1.Traverse the 2-D array to determine whether two points belong to a set;
//2.Belong to a set,union,[line] plus one; otherwise,union.  Mark the two points;
//3.compare the number of [line] and unmarked points
//patch: compare root and [line]
int makeConnected(int n, int** connections, int connectionsSize, int* connectionsColSize){
   //init

    int data[n];
    int flag[n];
    int line=0;
    int unlabel=n;   //计算未标记的值不正确。因为可能有多颗树，树之间也要连接
    int root=0;      //使用root 来标记待连接的点
    int i=0,j=0;
    int row=connectionsSize;
    int col=(*connectionsColSize);
    int forset=0;
    int first=0,second=0;
    int ** p=connections;

    for(i=0;i<n;i++){
        data[i]=-1;
        flag[i]=-1;
    }
    ds_init(data,n);

    //step 1

    for(i=0;i<row;i++){
        first=p[i][0];
        second=p[i][1];
        int r1=ds_find(data,n,first);
        int r2=ds_find(data,n,second);

        //step 2
        if(r1==r2){
            ds_union(data,n,first,second);
            line++;
        }
        else{
            ds_union(data,n,first,second);
        }
        flag[first]=1;
        flag[second]=1;
    }

    //step 3
    for(i=0;i<n;i++){
        //if(flag[i]==1)
        //    unlabel--;
        if(data[i]==-1)
            root++;
    }
    if(line>=(root-1)){
        return root-1;
    }
    else
        return -1;
}
/*
int main(){
    int conn[4][2]={{0,1},{0,2},{3,4},{2,3}};
    int n=5;
    int * p[4];
    p[0]=conn[0];
    p[1]=conn[1];
    p[2]=conn[2];
    p[3]=conn[3];

    int row=4;
    int col=2;
    int ret=makeConnected(n,p,row,&col);
    printf("answer = %d\n",ret);
}
*/
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

有个case 通不过（20220126已通过）。调试时候输入麻烦，可以用case下面几行代码替换方括号：

s1=s.replace('[','{')
s2=s1.replace(']','}')
print(s2)

1
2
3
4

2.优化及leetcode 547。

//the depth of root is -1.e.g. -3 means the depth of the root is 3
void ds_init_opti(int *data,int length){
    int i=0;
    for(i=0;i<length;i++){
        data[i]=-1;
    }
}

int ds_find_opti(int *data,int length,int num){
    if(data[num]==-1)
        return num;
    else{
        return data[num]=ds_find_opti(data,length,data[num]);
    }
}

void ds_union_opti(int *data,int length,int first,int second){
    int root1=ds_find_opti(data,length,first);
    int root2=ds_find_opti(data,length,second);
    if(root1==root2)
        return;
    int d1=data[root1];
    int d2=data[root2];
    if(d1<d2){  //root1 deeper
        data[root2]=root1;
    }
    else{      //root2 deeper
        data[root1]=root2;
    }
    return;
}

//1.traverse 2-D array p[i][j],data[n] set to -1
//2.if p[i][j]==1 union(i,j) marked(i,j);else continue
//3.calculate data[n] number of -1
int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize){
    int row=isConnectedSize;
    int col=(*isConnectedColSize);
    int **p=isConnected;
    int i=0,j=0;
    int n=row;
    int data[n];
    int ret=0;
    for(i=0;i<n;i++)
        data[i]=-1;
    //step 1
    for(i=0;i<row;i++){
        for(j=0;j<col;j++){
            //step 2
            if((i==j)||(p[i][j]==0)){
                continue;
            }
            else{
                int t1=ds_find_opti(data,n,i);
                int t2=ds_find_opti(data,n,j);
                if(t1!=t2){
                    ds_union_opti(data,n,i,j);
                }
            }
        }
    }
    //step 3
    for(i=0;i<n;i++){
        if(data[i]==-1)
            ret++;
    }
    return ret;
}
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
59
60
61
62
63
64
65
66
67
68