题目大意:多个块,如果一个块里有0,则这个块里所有人都是患者,如果里边的患者又在其他块里,那么另外一个块里的也都是患者,以此类推;
题解:很明显的并查集,用num[]数组记录之间的关系,先将num数组初始化为1,之后如果a和b之间有关系,将num[a]加到num[b]上,就相当于知道了多一个人是患者。这样每个点的记录数都是不一样的。
其他都是按模板,Union函数稍微改一下。
完整代码:
复制代码
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#include <iostream> #include <stdlib.h> using namespace std; #define MAX1 33000 int N,M; int pre[MAX1]; int num[MAX1]; void Init() { for(int i=0;i<N;i++) { pre[i]=i; num[i]=1; } } int find(int x) { int r=x; while(pre[r]!=r) r=pre[r]; return r; } void Union(int x,int y) { int a;int b; a=find(x); b=find(y); if(a!=b) { pre[a]=b; num[b]+=num[a]; } } int main() { int k; int a[MAX1]; while(cin>>N>>M,N||M) { Init();//刚开始忘了写这个,所以一直输出0; while(M--) { cin>>k; for(int j=0;j<k;j++) cin>>a[j]; for(int i=0;i<k-1;i++) Union(a[i],a[i+1]); } int k=find(0); cout<<num[k]<<endl; } return 0; }
最后
以上就是健忘豌豆最近收集整理的关于The Suspects (并查集)的全部内容,更多相关The内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复