[原创]HRBUST2189 并查集入门 节点的连接

2015-12-28 17:22:57 Tabris_ 阅读数：386

博客爬取于2020-06-14 22:45:13
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50420268

** 节点的连接 **

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 80 (43 users)

Total Accepted: 45 (41 users)

Rating:

Special Judge: No

** Description **

有N个节点，一开始任意两个节点都没有相连，之后有两种操作：

1: 将 A 节点和 B 节点连接起来。

2: 问从A节点出发可以直接或间接到达的节点数量。

如果 A 节点和 B 节点被连接起来了，那么从A可以到达B，同时从B也可以到达A。

** Input **

第一行是一个整数T，表示有T组测试数据。

对于每组测试数据，第一行是一个整数 n (n<=1000) 代表节点数，一个整数 m (m<=1000)代表操作数，之后有m行，每行代表一种操作。

第一种操作是:  0 A B  (1<=A,B<=n)，表示将A,B节点连接起来；

第二种操作是:  1 A    (1<=A<=n)，表示询问从A节点出发可以直接或间接到达的节点的数量。

** Output **

对于每组测试数据，如果是第二种操作，输出一个整数表示答案，每组输出占一行。

** Sample Input **

1

4 5

0 1

1 1 2

0 1

1 1 3

0 3

** Sample Output **

1

2

3

本题是一道简单的并查集问题

并查集主要就是有找到自己的上级 然后使两伙人合并到一伙

其中路径压缩是为使两伙归终于一个老大 而下级之间并不存在关心

本题没什么难的看看 代码注释就能理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <stdio.h>

#include <algorithm>

#include <string.h>

#include <iostream>

using namespace std;

int pre[1050];

void nimabi(int x)   //这个算初始化（自己是自己的老大）

{

   for(int i=1;i<=x;i++)

    {

       pre[i]=i;

    }

}

int find (int x)  //找老大

{

   int r=x;

   while(r!=pre[r])

    {

       r=pre[r];

    }

   int i=x,j;    //每个人（除了老大）都只有一个老大（老大不会再有老大）

   while(i!=r)

    {

       j=pre[i];

       pre[i]=r;

       i=j;

    }

   return r;

}

void join(int x,int y)//这个算是两个集体合伙了（但是老大只能有一个）

{

   int fx=find(x),fy=find(y);

   if(fx!=fy)

       pre[fx]=fy;

}

int main()

{

  int t;

  scanf("%d",&t);

  while(t--)

   {

      int n,m;

      scanf("%d%d",&n,&m);

      nimabi(n);

     /* for(int i=1;i<=n;i++)     //就是测试用来找老大的  便于理解

      printf("%d  ",find(i));

      printf("======\n");*/

      for(int i=0;i<m;i++)

      {

          int a;

          scanf("%d",&a);

          if(a==1)

          {

               int b,c;

              scanf("%d%d",&b,&c);

               join(b,c);

               /*for(int i=1;i<=n;i++)   //跟上面那个一个样

               printf("%d  ", find(i));

              printf("===========\n");*/

          }

          else

          {

               int d,sum=0;

               scanf("%d",&d);

               for(int j=1;j<=n;j++)

               {

                   if(find(d)==find(j)) sum++;

               }

               printf("%d\n",sum);

          }

      }

   }

}