poj1988

并查集 r[]记录节点到跟节点的距离 num[] 树的节点数

View Code

 1 #include <stdio.h>
 2 int father[30005],r[30005],num[30001];
 3 int find(int x)
 4 {
 5     if(x!=father[x])
 6     {
 7         int t = father[x];
 8         father[x] = find(father[x]);
 9         r[x]+=r[t];
10     }
11     return father[x];
12 }
13 
14 void union1(int x, int y)
15 {
16     father[y] = x;
17     r[y]+=num[x];
18     num[x]+=num[y] ;
19 
20 }
21 int main()
22 {
23     int n, i, j, x, y, k;
24     char c;
25     scanf("%d", &n);
26     for(i = 1 ; i <= 30000 ; i++)
27     {
28         father[i] = i;
29         r[i] = 0;
30         num[i] = 1;
31     }
32     while(n--)
33     {
34         getchar();
35         scanf("%c", &c);
36         if(c == 'M')
37         {
38             scanf("%d%d", &x,&y);
39             int pa = find(x);
40             int pb = find(y);
41             if(pa!=pb)
42             {
43                 union1(pa,pb);
44             }
45         }
46         else
47         {
48             scanf("%d", &x);
49             y = find(x);
50             printf("%d\n", num[y]-r[x]-1);
51         }
52     }
53     return 0;
54 }

View Code

 1 #include <stdio.h>
 2  int father[30005],r[30005],num[30001];
 3  int find(int x)
 4  {
 5      if(x!=father[x])
 6      {
 7          int t = father[x];//这个跟下面的那条不能反 保证t不为跟节点
 8          father[x] = find(father[x]);//回溯时把节点都指向根节点  方便下次查找     
 9          r[x]+=r[t];
10      }
11      return father[x];
12  }
13 
14  void union1(int x, int y)
15  {
16      father[y] = x;
17      r[y]+=num[x];
18      num[x]+=num[y] ;
19 
20  }
21  int main()
22  {
23      int n, i, j, x, y, k;
24      char c;
25      scanf("%d", &n);
26      for(i = 1 ; i <= 30000 ; i++)
27      {
28          father[i] = i;
29          r[i] = 0;
30          num[i] = 1;
31      }
32      while(n--)
33      {
34          getchar();
35          scanf("%c", &c);
36          if(c == 'M')
37          {
38              scanf("%d%d", &x,&y);
39              int pa = find(x);
40              int pb = find(y);
41              if(pa!=pb)
42              {
43                  union1(pa,pb);
44              }
45          }
46          else
47          {
48              scanf("%d", &x);
49              y = find(x);
50              printf("%d\n", num[y]-r[x]-1);
51          }
52      }
53      return 0;
54  }