题目链接:zoj1789
复制代码
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/* 题目大意: n个人,m个小组,每个人可以加入多个小组,找出与0有关系的人 跟0在同一个组人和0有关系,如果一个与和0有关系的人在同一组,那么 这个人和0有关系,如:0,2为一组,2,5为一组,那么2和5都和0有关系 思路:并查集 */ #include <iostream> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <cstdlib> #include <string> using namespace std; const int N = 3e4 + 10; int father[N]; void set(int n) { for(int i = 0; i < n; i ++) father[i] = i; } int find(int x) { if(x == father[x]) return x; return father[x] = find(father[x]); } void Union(int x, int y) { x = find(x); y = find(y); if(x < y) father[y] = x; else father[x] = y; } int main() { int n,m,t,x,y,i; while(scanf("%d%d",&n,&m),(n+m)) { set(n); while(m--) { scanf("%d%d",&t,&x); for(i = 1; i < t; i ++) { scanf("%d",&y); Union(x, y);//将每一行的第一个元素作为父节点 } } int ans = 1; for(i = 1; i < n; i ++) { //不能直接用father[i] == father[0] 来判断 //因为后输入的值在合并的时候可能会作为之前一些父节点的父节点 if(find(0) == find(i)) ans ++; } printf("%dn",ans); } return 0; }
最后
以上就是现代向日葵最近收集整理的关于zoj1789The Suspects(简单并查集)的全部内容,更多相关zoj1789The内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复