POJ 1611

作者: 与卿__歌 | 来源:发表于2017-01-17 23:06 被阅读0次

The Suspects

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
题意:
0是公认的怀疑人,和他一组的也算是怀疑人,被怀疑的一组的人在其他组,那么他们也变成怀疑人了。
思路:联通块问题,把一个组的连一起,组里的人在其他组,也连起来。然后找和0连起来的人。

#include<stdio.h>
int s1[30005];
int find(int x)
{
    if(x==s1[x])
    return x;
    else
    return s1[x]=find(s1[x]);
}
int main()
{
    int n,m,i,j,s,count,t,x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)
        break;
            for(i=0;i<=n;i++)
        {
            s1[i]=i;
        }
    
        for(i=0;i<m;i++)
        {
            scanf("%d",&t);
            scanf("%d",&x);     //把一个组连在一起
            
                for(j=1;j<t;j++)
                {
                    scanf("%d",&y);
                    x=find(x);
                    y=find(y);
                    if(x!=y)
                    {
                        s1[x]=y;
                    }
                }
            
        }
        s=find(0);
        count=0;
        for(j=0;j<n;j++)
        {
            if(s==find(j))     //找和0连起来的数字
            {
                count++;
            }
        }
        printf("%d\n",count);   
    }
} 

相关文章

  • 再贴一次并查集

    F - The Suspects POJ - 1611

  • POJ 1611 - The Suspects

    POJ 1611 - The Suspects Severe acute respiratory syndrome...

  • POJ 1611

    POJ 1611 题意 有n个人参加了m个社团,同一个社团互相接触的人有感染非典的概率,已知0号同学是疑似病例,求...

  • POJ 1611

    POJ 1611 题意 有n个人参加了m个社团,同一个社团互相接触的人有感染非典的概率,已知0号同学是疑似病例,求...

  • POJ 1611

    The Suspects Severe acute respiratory syndrome (SARS), an...

  • 2019-01-29 [POJ-1611],

    [POJ-1611] include include using names...

  • POJ——1611 The Suspects

    题目大意 这题将的就是有n个人,被分成m组(每个人可能在几个组里面),其中0号人物肯定是患有非典。而与0号同组的人...

  • The Suspects POJ - 1611

    Severe acute respiratory syndrome (SARS), an atypical pne...

  • POJ-1611 The Suspects

    1、题意## 为了防止SARA传播,NSYSU收集所有学生组的成员列表,一旦群组中的成员是可疑人员,群组中的所有成...

  • Chapter9——图——最小生成树

    1. 题目列表 POJ1789(prim算法) POJ2485(prim) POJ1258(prim) POJ30...

网友评论

      本文标题:POJ 1611

      本文链接:https://www.haomeiwen.com/subject/zjxvbttx.html