并查集

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 const int max_n = 1000;
 7 
 8 int par[max_n];
 9 int ranks[max_n];
10 
11 void init(int n)
12 {
13     for(int i=0;i<n;++i)
14     {
15         par[i]=i;
16         ranks[i]=0;
17     }
18 }
19 
20 int find(int x)
21 {
22     if(par[x]==x)
23     {
24         return x;
25     }
26     else
27     {
28         return par[x]=find(par[x]);
29     }
30 }
31 
32 
33 // 合并
34 void unite(int x,int y)
35 {
36     x=find(x);
37     y=find(y);
38     if(x==y)
39     {
40         return;
41     }
42 
43     if(ranks[x]<ranks[y])
44     {
45         par[x]=y;
46     }
47     else
48     {
49         par[y]=x;
50         if(ranks[x]==ranks[y])
51         {
52             ++ ranks[x];
53         }
54     }
55 }
56 
57 
58 bool same(int x,int y)
59 {
60     return find(x)==find(y);
61 }
62 
63 
64 int main()
65 {
66 
67     return 0;
68 }