并查集

 1 #include<stdio.h>
 2 int n,m,parent[200010],rank[200010];
 3 
 4 //初始化函数 
 5 void chushihua()
 6 {
 7     for (int i = 0; i <= n; i++)
 8     {    parent[i] = i;
 9         rank[i] = 1;
10     }
11 }
12 
13 //找根函数 
14 int  root_search(int t)
15 {
16     while(parent[t] != t)
17     {
18         t = parent[t];
19         rank[t]++;
20     }
21     return t;
22 }
23 
24 //合并函数 
25 void merge(int u,int v)
26 {
27     int t1 = root_search(u);
28     int t2 = root_search(v);
29     if (t1 != t2){
30         if (rank[t1] > rank[t2])    parent[t2] = t1;
31         else    parent[t2] = t1;
32         
33     }    
34 }
35 
36 //主函数 
37 int main()
38 {
39     scanf("%d%d",&n,&m);
40     int k,index = 0;
41     chushihua();
42     for (int i = 0; i < m; i++)
43     {
44         scanf("%d",&k);
45         if (k == 2)
46         {
47             int A,B;
48             scanf("%d%d",&A,&B);
49             A = root_search(A);
50             B = root_search(B);
51             if (A == B)        printf("Y\n");
52             else    printf("N\n");
53         } 
54         else 
55         {
56             int A,B;
57             scanf("%d%d",&A,&B);
58             merge(A,B);
59         }
60     }
61     return 0;
62 }