今天简单看了下并查集，关于优化什么的还没有看。做了两个简单的题，先熟悉一下~
并查集用来表示若干互不相交的集合，是一种树状的结构。
并查集有三个操作：初始化，合并，查询。
其中在合并的时候，由于可能集合是一个偏的很厉害的树，如果不加分类直接合并的话，每次查询会相当浪费时间，所以
需要每次合并的时候将规模小的集合并到规模大的集合，并且随时更新集合内元素的个数。
简单的不优化的Union函数如下：
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 }
优化后的Union函数如下：
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 ; //只有当两个根节点的祖先不同才合并
7 if(t1!=t2){
8 if(a[t1].v<a[t2].v){ //将规模小的集合并到规模大的集合，同时集合元素个数增加
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 }
先看一下最简单的并查集的模板：
1 #include<stdio.h>
2 #define MAX 10002
3 int m,n;
4 struct type
5 {
6 int father,v; //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; //初始化将集合节点标记为自己，元素个数为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 ; //只有当两个根节点的祖先不同才合并
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 {}
运用上边的模板，就可以将TOJ 3499 AC掉了
题意大概是N个数，从0到N-1，有M个关系，最后问P和Q之间是否是关系。
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 }