﻿ 粗略并查集2_www.bifa688.com >

# 粗略并查集2

- 编辑：www.bifa688.com -

The Suspects

 Time Limit: 1000MS Memory Limit: 20000K Total Submissions: 42098 Accepted: 20311

The Suspects

Description

## B - The Suspects

POJ - 1611

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.

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

有N个学生，分成m个组（一个学生可以分别进入多个组）
分别输入m个组的成员个数k和成员
只要是每组中有一个人得了传染病那么整个组都会有传染病

``````

基本并查集模板，参加个数管理间接重回就ok

``````#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<algorithm>
#include<map>
#define maxn 100005
using namespace std;
int fa[maxn],rank[maxn];
void init(int n)
{
for(int i=0;i<n;i  )
{
fa[i]=i;
rank[i]=1;
}
}
int find(int x)
{
if(fa[x]==x)return x;
else{
return fa[x]=find(fa[x]);
}
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)return ;
if(x!=y)
{
fa[x]=y;
rank[y] =rank[x];
}
/*if(rank[x]<rank[y])
{
fa[x]=y;
rank[x] =rank[y];
}
else{
fa[y]=x;
rank[y] =rank[x];
// if(rank[x]==rank[y])rank[x]  ;
}
*/
}
int main()
{
int n,m,k;
int s[maxn];
while(cin>>n>>m){
init(n);
if(n==0&&m==0)return 0;
while(m--)
{
cin>>k;
for(int i=0;i<k;i  )
{
cin>>s[i];
}
for(int i=0;i<k-1;i  )
{
unite(s[i],s[i 1]);
}
}
int t=find(0);
cout<<rank[t]<<endl;
}
return 0;
}
``````

PS:

**Time Limit: 1000MS　　Memory Limit: 20000K**

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.

**Total Submissions: 48698　　Accepted: 23286**

Input

Description

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.

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003.

Output

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,

For each case, output the number of suspects in one line.

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

Sample Input

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.

``````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
``````

Input

Sample Output

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.

``````4
1
1
``````

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

Source

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

Asia Kaohsiung 2003

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
``````
`````` 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <queue>
6 #include <vector>
7 #define max(a, b) ((a) > (b) ? (a) : (b))
8 #define min(a, b) ((a) < (b) ? (a) : (b))
9
11 {
12     x = 0;char ch = getchar(), c = ch;
13     while(ch < '0' || ch > '9')c = ch, ch = getchar();
14     while(ch <= '9' && ch >= '0')x = x * 10   ch - '0', ch = getchar();
15     if(c == '-')x = -x;
16 }
17
18 const int MAXN = 100000   10;
19
20 int n, m, fa[MAXN], ans;
21
22 int find(int x)
23 {
24     return x == fa[x] ? x : fa[x] = find(fa[x]);
25 }
26
27 int main()
28 {
29     register int pre,now,tmp,f1,f2;
30     while(scanf("%d %d", &n, &m) && n   m)
31     {
32         ans = 0;
33         for(register int i = 1;i <= n;   i)fa[i] = i;
34         for(register int i = 1;i <= m;   i)
35         {
38             f1 = find(pre);
39             for(register int j = 2;j <= tmp;   j)
40             {
42                 f2 = find(now);
43                 fa[f2] = f1;
44             }
45         }
46         f1 = find(1);
47         for(register int i = 1;i <= n;   i)
48         {
49             int k = find(i);
50             ans  = (f1 ==k);
51         }
52         printf("%dn", ans);
53     }
54     return 0;
55 }
``````

Sample Output

POJ1611

``````4
1
1
``````

Source

Asia Kaohsiung 2003

高校要寻找患了SAHighlanderS一共有微微人，n个学生人数（编号0~n-一），m个协会，每一个协会有k个人，并提交那k个人的号子。

输入：第贰行n（学生人数）和m（组织数），接下去m行，每行第3个数代表k，接下去k个数代表在座此协会的上学的儿童的编号，

n==m==0时表示结束。

输出：患病学生人数

并查集，大家把每一种协会的学生的号码整合起来放在同等棵树上，若三个学生参与了多少个组织，则他所参组织的多棵树会被合并起来成为一棵，**如此那般结尾只供给找寻号码为0的学员所在的树的结点数正是患有学生的总人口了。**

值得注意的是，代码中对寻找根节点的算法进行了优化！

原来只是独自的追寻有些结点所在树的根节点，并从未改换数的构造：

``````　　return node==student[node]?node:find_Father(student[node]);
``````

优化后，改造了树的布局，将结点至根节点的链上的享有结点直接指向了根节点，大大方便了下一次重新寻觅的功效！

``````　　static int find_Father(int node) {    //寻找根节点
/*
return node==student[node]?node:find_Father(student[node]);
*/

if(node!=student[node]) {
student[node]=find_Father(student[node]);
//状态压缩，将结点node到根节点这条链上的结点直接指向根节点，优化下次寻找根节点的时间
}
return student[node];

}
``````

Java代码：

``````import java.util.*;

public class TheSuspects {

static int n;    //学生数量
static int m;    //组的数量
static int student[];
static int book[];

static int find_Father(int node) {    //寻找根节点
/*
return node==student[node]?node:find_Father(student[node]);
*/

if(node!=student[node]) {
student[node]=find_Father(student[node]);
//状态压缩，将结点node到根节点这条链上的结点直接指向根节点，优化下次寻找根节点的时间
}
return student[node];

}

public static void main(String[] args) {

ArrayList list=new ArrayList();
int count=0;

if(n==0 && m==0) {
break;
}
student=new int[n];
book=new int[n];
for(int i=0;i<n;i  ) {
student[i]=i;    //学生指向自己
book[i]=1;    //每个学生为1个结点
}
for(int i=1;i<=m;i  ) {
for(int j=1;j<=k-1;j  ) {
int father_One=find_Father(node_One);    //找出父节点
int father_Two=find_Father(node_Two);
if(father_One!=father_Two) {
student[father_Two]=father_One;    //合并
book[father_One] =book[father_Two];    //book[根节点]存储其所在树的结点数，每有一个学生加入此数，总结点数 1
}
}
}
count  ;

}
for(int i=0;i<count;i  ) {
System.out.println(list.get(i));
}
}

}
``````

POJ截图：

23:31:36

2018-07-18