【并查集】The Suspects POJ-1611
打算尝试一种新写法
我愿叫它“蒟蒻的level++”
写下我的心路历程
Description
Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.
题目大意
SARS来了，找密接。0号是确诊，要找到0号的密接和0号的密接的密接
Input
The input file contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n?1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.
Output
For each case, output the number of suspects in one line.
Sample Input
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sample Output
4
1
1
我本来以为这个是普通的并查集
无非是在输入时候做点小动作
把一个组的人加在一起就行了
但是WA
绷不住了，上网查题解
老哥说：找一个“大哥”，组里的跟“大哥”的根节点走
有道理啊，但是平常这样就不行吗？
回去看我的码，感觉不太对劲。我那样是把最后一个成员当了“大哥”了，
万一最后一个成员洁身自好呢？
下面是代码1
#include
#define N 40000
using namespace std;
int fa[N];
void init(int n){
for(int i=0;i<=n;i++){
fa[i]=i;
}
}
int find(int x){
if(fa[x]==x) return x;
else{
fa[x]=find(fa[x]);
return fa[x];
}
}
void unin(int x,int y){
int rx=find(x);
int ry=find(y);
if(rx!=ry) fa[rx]=ry;
}
int main(){
int m,n;
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0&&m==0) return 0;
init(n);
for(int i=1;i<=m;i++){
int num,tmp;
cin>>num>>tmp;
for(int j=1;j<=num-1;j++){
int a;
cin>>a;
unin(tmp,a);
}
}
int cnt=0;
for(int i=0;i<=n-1;i++){
if(fa[i]==fa[0]) cnt++;
}
cout< 这个码WA了，很惨。
我上网找大佬，感谢https://blog.csdn.net/iDaybreak/article/details/80414387?spm=1001.2101.3001.4242.1
他属于是具体问题具体分析
下面是他的想法
解体思路：每个数都有一个自己的团体，如果两个数相遇了，且他俩不属于同一个团体，就要进行吞并（大鱼吃小鱼）。为什么呢？因为一旦两个数相遇，就说明不管是两个团体中的谁感染了，这两个团体中的所有人都要被列为嫌疑人，也就是说，相遇即为一体。
操作方法：一个团体中的数很多，为了保证简便，所以在每个团体中都选出了一个老大，老大掌管他的团体中有多少人，当不同的团体之间进行比较时，都是拿老大进行比较，看看谁是大鱼谁是小鱼。
解法正确性原因：不断的更新每个团体的情况，团体中的每一个数都可以进行组织的更新，使得遍历一边之后，每个数都可以直接找到他所在团体的老大，进而查询到该团体中由多少人。
版权声明：本文为CSDN博主「Reversing」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/iDaybreak/article/details/80414387
我结合了他的想法改进了我的代码
以下是AC代码
#include
#define N 40000
using namespace std;
int fa[N],grp[N];
void init(int n){
for(int i=0;i<=n;i++){
fa[i]=i;
grp[i]=1;
}
}
int find(int x){
if(fa[x]==x) return x;
else{
fa[x]=find(fa[x]);
return fa[x];
}
}
void unin(int x,int y){
int rx=find(x);
int ry=find(y);
if(rx!=ry){
if(grp[rx]<=grp[ry]){
grp[ry]+=grp[rx];
fa[rx]=ry;
}
if(grp[ry]<=grp[rx]){
grp[rx]+=grp[ry];
fa[ry]=rx;
}
}
}
int main(){
int m,n;
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0&&m==0) return 0;
init(n);
for(int i=1;i<=m;i++){
int num,tmp;
cin>>num>>tmp;
for(int j=1;j<=num-1;j++){
int a;
cin>>a;
unin(tmp,a);
}
}
cout<