并查集

并查集常用代码

 1 #include<stdio.h>
 2 #define MAX 11
 3 
 4 
 5 int father[MAX];   /* father[x]表示x的父节点*/
 6 int rank[MAX];     /* rank[x]表示x的秩*/
 7 
 8 
 9 /* 初始化集合*/
10 void Make_Set(int x)
11 {
12     father[x] = x; //根据实际情况指定的父节点可变化
13     rank[x] = 0;   //根据实际情况初始化秩也有所变化
14 }
15 
16 
17 
18 
19 //查找父节点
20 int find(int x)
21 {
22     return father[x] == x ? x : find(father[x]);
23 }
24 
25 //查找
26 int find1(int a)
27 {
28     int r=a;
29     while(f[r]!=r)  r=f[r];
30     return r;
31 }
32 
33 /* 查找x元素所在的集合,回溯时压缩路径*/
34 int Find_Set(int x)
35 {
36     if (x != father[x])
37     {
38         father[x] = Find_Set(father[x]); //这个回溯时的压缩路径是精华
39     }
40    return father[x];
41 }
42 
43 void find2(int a)
44 {
45     int i,j,r;
46     r=a;
47     while(f[r]!=r)
48         r=f[r];
49     i=a;
50     while(i!=r)
51     {
52         j=f[i];
53         f[i]=r;
54         i=j;
55     }
56 }
57 
58 
59 
60 
61 //创建并查集
62 void merge(int a,int b)
63 {
64     int A,B;
65     A=find(a);
66     B=find(b);
67     if(A!=B)
68         father[B]=A;
69 }
70 
71 void Union(int x, int y)
72 {
73     x = Find_Set(x);
74     y = Find_Set(y);
75     if (x == y) return;
76     if (rank[x] > rank[y]) 
77     {
78         father[y] = x;
79     }
80     else
81     {
82         if (rank[x] == rank[y])
83         {
84             rank[y]++;
85         }
86         father[x] = y;
87     }
88 }

//查找并压缩的非递归实现
int find1(int a)
{
    int i,j,r;
    r=a;
    while(f[r]!=r)
        r=f[r];
    i=a;
    while(i!=r)
    {
        j=f[i];
        f[i]=r;
        i=j;
    }
    return r;
}
//查找并压缩的非递归实现
int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}