[原创]HRBUST2189 并查集入门 节点的连接
[原创]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=0;i<m;i++)
{
int a;
scanf("%d",&a);
if(a==1)
{
int b,c;
scanf("%d%d",&b,&c);
join(b,c);
}
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);
}
}
}
}
|
