并查集及其应用

并查集初步

PS:今天入手了一台1993年产的IBM Model M弹簧轴机械键盘，真好用呀真好用~ ^_^

并查集经常借助树形数据结构来实现。

设Father[i]表示元素i所属于的集合编号。初始化Father[x]=x;即每个节点都是单独的一棵树

并查集具有两项基本操作：

Find(i) ：返回元素i所属于的集合的编号

Int Find(int x)

{

If (x!=Father[x])

Father[x]=Find(Father[x]) //此处用到了路径压缩优化

Return Father[x];

}

Union(x,y)：合并元素x和元素y所在的集合

Void Union(int x,int y)

{

Int fx=Find(x);

Int fy=Find(y);

If (fx!=fy)

Father[fy]=fx;

}

来看一个简单的例题：

Eg1：亲戚（原题网上一抓一大把T^T）

赤裸裸的并查集，不再解释了~

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 int n,m,p,tx,ty,i,x,y,j;
 5 int f[10000];
 6 
 7 int find(int x)
 8 {
 9     if (f[x]!=x)
10         f[x]=find(f[x]);
11     return f[x];
12 }
13 
14 void iunion(int x,int y)
15 {
16     int fx,fy;
17     fx=find(x);
18     fy=find(y);
19     if (fx!=fy) 
20         f[fx]=fy;
21 }
22 
23 int main()
24 {
25     cin>>n>>m>>p;
26     memset(f,0,sizeof(f));
27     for (i=1;i<=n;i++)
28         f[i]=i;
29         
30     for (i=1;i<=m;i++)
31     {
32         cin>>x>>y;
33         iunion(x,y);
34             for (j=1;j<=n;j++)  cout<<f[j]<<"  ";
35             cout<<endl;
36     }
37         
38     for (i=1;i<=p;i++)
39     {
40         cin>>x>>y;
41         tx=find(x);
42         ty=find(y);
43         if (tx==ty) cout<<"yes"<<endl;
44             else cout<<"no"<<endl;
45     }
46 }

View Code

Eg2：代码等式（原题见《算法艺术与信息学竞赛》P80 例题1）

Solution：先将表达式中的字母按照a1、a2、a3、b1、b2……这样的形式展开，然后一一对应匹配即可。

注意几个问题：

C语言中的数组下标不能为负值，只能从0开始 T^T
求字符的ASCII：用强制类型转换：

　　　　　　Char c=’a’

　　　　　　Int i=c; //那么i的值即’a’的ASCII码97

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 
  6 int visited[1000];
  7 int lth[1000];
  8 int father[1000];
  9 int ch[2][1000];
 10 char s1[1000],s2[1000];
 11 int i,j,k,l1,l2,t1,t2,tmp,sum;
 12 
 13 int find(int x)
 14 {
 15     if (x!=father[x])
 16         father[x]=find(father[x]);
 17     return father[x];
 18 }
 19 
 20 void iunion(int x,int y)
 21 {
 22     int fx=find(x);
 23     int fy=find(y);
 24     if (fx!=fy)
 25         father[fy]=fx;
 26 }
 27 
 28 int main()
 29 {
 30     cin>>k;
 31     sum=0;
 32     for (i=1;i<=k;i++) 
 33     {
 34         cin>>lth[i];
 35         sum=sum+lth[i];    
 36     }
 37     cin>>s1;    cin>>s2;
 38     l1=strlen(s1);
 39     l2=strlen(s2);
 40     
 41     t1=1;
 42     for (i=0;i<l1;i++)
 43     {
 44         char tch=s1[i];
 45         switch (tch)
 46         {
 47         case '0':
 48             ch[1][t1]=0;
 49             t1++;
 50         case '1':
 51             ch[1][t1]=sum+1;
 52             t1++;
 53         default:
 54             int ci=tch;
 55              ci=ci-97+1;
 56              tmp=0;
 57              for (j=1;j<=ci-1;j++)
 58                  tmp=tmp+lth[j];
 59              tmp++;
 60              for (j=1;j<=lth[ci];j++)
 61              {
 62                  ch[1][t1]=tmp;
 63                  tmp++;
 64                  t1++;
 65              }
 66         }
 67     }
 68     
 69     t2=1;
 70     for (i=0;i<l2;i++)
 71     {
 72         char tch=s2[i];
 73         switch (tch)
 74         {
 75         case '0':
 76             ch[2][t2]=0;
 77             t2++;
 78         case '1':
 79             ch[2][t2]=sum+1;
 80             t2++;
 81         default:
 82             int ci=tch;
 83              ci=ci-97+1;
 84              tmp=0;
 85              for (j=1;j<=ci-1;j++)
 86                  tmp=tmp+lth[j];
 87              tmp++;
 88              for (j=1;j<=lth[ci];j++)
 89              {
 90                  ch[2][t2]=tmp;
 91                  tmp++;
 92                  t2++;
 93              }
 94         }
 95     }
 96     t1--;    t2--;
 97     
 98     //FOR DEBUG ONLY  >:>
 99     cout<<t1<<endl;
100     for (i=1;i<=t1;i++)        cout<<ch[1][i]<<" ";
101     cout<<endl;
102     cout<<t2<<endl;
103     for (i=1;i<=t2;i++)     cout<<ch[2][i]<<" ";
104     cout<<endl;
105     cout<<sum<<endl;
106     cout<<"****************************************************"<<endl;
107     
108     memset(father,0,sizeof(father));
109     for (i=1;i<=sum+1;i++)
110         father[i]=i;
111         
112     for (i=1;i<=t1;i++)
113         iunion(ch[1][i],ch[2][i]);
114     int ans=1;        
115     t1=find(0);    t2=find(sum+1);
116     ////cout<<t1<<"   "<<t2<<endl;
117     memset(visited,0,sizeof(visited));
118     visited[t1]=1;    visited[t2]=1;
119     for (i=1;i<=sum;i++)
120     {
121         tmp=find(i);
122         if (!visited[tmp])
123         {
124             visited[tmp]=1;
125             ans=ans*2;
126         }
127     }
128     cout<<ans<<endl;
129 }

View Code

Eg3：用并查集实现kruskal算法

 1 #include <iostream>
 2 using namespace std;
 3 
 4 struct abc
 5 {
 6     int x,y,dat;
 7 };
 8 
 9 struct abc e[1000];
10 int f[1000];
11 int i,j,k,ans,n,m,tx,ty,tmp;
12 
13 int find(int x)
14 {
15     if (x!=f[x])
16         f[x]=find(f[x]);
17     return f[x];
18 }
19 
20 void iunion(int x,int y)
21 {
22     int fx=find(x);
23     int fy=find(y);
24     if (fx!=fy)
25         f[fy]=fx;
26 }
27 
28 void qsort(int l,int r)
29 {
30    int i,j,mid;
31    struct abc t; 
32    i=l;
33    j=r;
34    mid=e[(l+r)/2].dat;
35    do{
36        while (e[i].dat<mid) i++;
37        while (e[j].dat>mid) j--;
38        if (!(i>j))
39        {
40            t=e[i];
41            e[i]=e[j];
42            e[j]=t;
43            i++;
44            j--;
45        }
46    }while (i<=j);
47    if (l<j) qsort(l,j);
48    if (i<r) qsort(i,r);
49 }
50 
51 int main()
52 {
53     
54     cin>>n>>m;
55     for (i=1;i<=m;i++)
56     {
57         cin>>tx>>ty>>tmp;
58         e[i].x=tx;
59         e[i].y=ty;
60         e[i].dat=tmp;
61     }
62 
63     for (i=1;i<=n;i++)
64         f[i]=i;
65     qsort(1,m);
66     
67     k=1;
68     ans=0;
69     for (i=1;i<=n-1;i++)
70     {
71         while (find(e[k].x)==find(e[k].y)) k++;
72         iunion(e[k].x,e[k].y);
73         ans=ans+e[k].dat;
74         cout<<e[k].x<<" "<<e[k].y<<" "<<e[k].dat<<endl;
75     }
76     
77     cout<<ans<<endl;
78 }

View Code