今天簡(jiǎn)單看了下并查集，關(guān)于優(yōu)化什么的還沒(méi)有看。做了兩個(gè)簡(jiǎn)單的題，先熟悉一下~
并查集用來(lái)表示若干互不相交的集合，是一種樹(shù)狀的結(jié)構(gòu)。
并查集有三個(gè)操作：初始化，合并，查詢。
其中在合并的時(shí)候，由于可能集合是一個(gè)偏的很厲害的樹(shù)，如果不加分類直接合并的話，每次查詢會(huì)相當(dāng)浪費(fèi)時(shí)間，所以
需要每次合并的時(shí)候?qū)⒁?guī)模小的集合并到規(guī)模大的集合，并且隨時(shí)更新集合內(nèi)元素的個(gè)數(shù)。
簡(jiǎn)單的不優(yōu)化的Union函數(shù)如下：
1 Union(int root1,int root2)
2 {
3 int t1,t2;
4 t1=find(root1);
5 t2=find(root2);
6 if(t1!=t2)
7 t1.father=t2;
8 return ;
9 }
優(yōu)化后的Union函數(shù)如下：
1 void Union(int root1,int root2)
2 {
3 int t1,t2;
4 t1=find(root1);
5 t2=find(root2);
6 if(t1==t2) return ; //只有當(dāng)兩個(gè)根節(jié)點(diǎn)的祖先不同才合并
7 if(t1!=t2){
8 if(a[t1].v<a[t2].v){ //將規(guī)模小的集合并到規(guī)模大的集合，同時(shí)集合元素個(gè)數(shù)增加
9 a[t1].father=t2;
10 a[t2].v+=a[t1].v;
11 }
12 else{
13 a[t2].father=t1;
14 a[t1].v+=a[t2].v;
15 }
16
17 }
18 }
先看一下最簡(jiǎn)單的并查集的模板：
1 #include<stdio.h>
2 #define MAX 10002
3 int m,n;
4 struct type
5 {
6 int father,v; //father 表示根節(jié)點(diǎn)，v表示集合內(nèi)元素個(gè)數(shù)
7 }a[MAX];
8 void initial(int n)
9 {
10 int i;
11 for(i=0;i<n;i++){
12 a[i].father=i; //初始化將集合節(jié)點(diǎn)標(biāo)記為自己，元素個(gè)數(shù)為1
13 a[i].v=1;
14 }
15 }
16 int find(int n)
17 {
18 if(a[n].father!=n)
19 return find(a[n].father); //此處也可以寫為 while(a[n].father!=n) n=a[n].father;
20 return n;
21 }
22 void Union(int root1,int root2)
23 {
24 int t1,t2;
25 t1=find(root1);
26 t2=find(root2);
27 if(t1==t2) return ; //只有當(dāng)兩個(gè)根節(jié)點(diǎn)的祖先不同才合并
28 if(t1!=t2){
29 if(a[t1].v<a[t2].v){ //將規(guī)模小的集合并到規(guī)模大的集合，同時(shí)集合元素個(gè)數(shù)增加
30 a[t1].father=t2;
31 a[t2].v+=a[t1].v;
32 }
33 else{
34 a[t2].father=t1;
35 a[t1].v+=a[t2].v;
36 }
37 }
38 }
39 int main()
40 {}
運(yùn)用上邊的模板，就可以將TOJ 3499 AC掉了
題意大概是N個(gè)數(shù)，從0到N-1，有M個(gè)關(guān)系，最后問(wèn)P和Q之間是否是關(guān)系。
Code：
1 #include<stdio.h>
2 #define MAX 10002
3 int m,n;
4 struct type
5 {
6 int father,v;
7 }a[MAX];
8 void initial(int n)
9 {
10 int i;
11 for(i=0;i<n;i++){
12 a[i].father=i;
13 a[i].v=1;
14 }
15 }
16 int find(int n)
17 {
18 if(a[n].father!=n)
19 return find(a[n].father);
20 return n;
21 }
22 void Union(int root1,int root2)
23 {
24 int t1,t2;
25 t1=find(root1);
26 t2=find(root2);
27 if(t1==t2) return ;
28 if(t1!=t2){
29 if(a[t1].v<a[t2].v){
30 a[t1].father=t2;
31 a[t2].v+=a[t1].v;
32 }
33 else{
34 a[t2].father=t1;
35 a[t1].v+=a[t2].v;
36 }
37 }
38 }
39 int main()
40 {
41 int cas,i,j,k,p,q,N,M;
42 while(scanf("%d%d%d",&N,&M,&k)!=EOF){
43 initial(N);
44 for(i=0;i<M;i++){
45 scanf("%d%d",&p,&q);
46 Union(p,q);
47 }
48 for(i=1;i<=k;i++){
49 scanf("%d%d",&p,&q);
50 if(find(p)==find(q))
51 printf("YES\n");
52 else printf("NO\n");
53 }
54 }
55 }