首页 > 代码库 > The Suspects POJ1611

The Suspects POJ1611

2024-09-08 23:25:14   219人阅读

The Suspects
Time Limit: 1000MS   Memory Limit: 20000K
Total Submissions: 36417   Accepted: 17681

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.

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

Source

Asia Kaohsiung 2003
这个题目的意思是。。。老规矩，根据输入开始讲，嘿嘿，首先输入n代表有n个人，输入m代表接下来有m组人，其中0是SARS病毒感染者，我们得找出到底有几个SARS病毒感染嫌疑人，只要与0接触或间接接触的都是SARS病毒感染嫌疑人（包括0本身哦），所以我们得找出有几个与0接触或间接接触的人。
嗯。。方法呢，就是首先找到0所在的小组，然后以这个小组内与0接触的人开始每个与他们接触的人都要加入0所在的小组（集合，用join），最后就是判断这个小组有几个人就可以了。可以存在一个数组里面哦。
这里是我写这道题目参考的博客，写的很好哦，就是因为看了这篇博客我才写出来的。。。
http://blog.csdn.net/tiantangrenjian/article/details/7084609
这篇博客还有并查集的详解哦
再插入一个讲并查集讲的很好简单易懂的博客吧
http://blog.csdn.net/dellaserss/article/details/7724401/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pre[30010],num[30010];
int findn(int x)
{
    if(x!=pre[x])
        pre[x] = findn(pre[x]);
    return pre[x];//注意这里是pre[x]
}
void join(int x,int y)
{
    int fx=findn(x),fy=findn(y);
    if(fx!=fy)
    {
        if(num[fx]>=num[fy])
        {
            pre[fy] = fx;
            num[fx] = num[fx] + num[fy];//跟新num
        }
        else
        {
            pre[fx] = fy;
            num[fy] = num[fy] + num[fx];
        }
    }
}
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        if(n==0&&m==0)
            break;
        for(int i=0;i<n;i++)
            pre[i]=i,num[i]=1;//先初始化
        while(m--)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            for(int i=1;i<a;i++)
            {
                int c;
                scanf("%d",&c);
                join(b,c);//以每组第一个建立一个小组集合
            }
        }
        printf("%d\n",num[pre[0]]);
    }
    return 0;
}

 

The Suspects POJ1611


联系
我们