POJ 1611

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);   
    }
} 
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,959评论 0 23
  • 秋,吹落最后一片树叶 树叶带着思恋,飘啊飘啊 穿过丛林,越过小溪 飘落在少年的那双白球鞋上 少年拾起树叶 看着远方...
    南城旧馆阅读 157评论 2 1
  • 01“你觉得嫁给爱情是种什么体验?”21岁的表妹躺着沙发上闷闷地问我。这是她失恋后第57次向我发问,之前还问过“怎...
    冷爱阅读 294评论 0 0
  • 紧合双目却比睁眼现实,炯炯圆睁又如蒙闭愚昧,或许,就是文人和其他人的区别。 人们活在当下,就好比一场恢宏的即兴表演...
    吾欲阅读 270评论 0 1
  • 权谋从哪来? 有位网友问了我2个问题,什么样的公司不玩权术?为什么30岁了发现自己怂了? 我发现只有一种人,无需玩...
    诸葛司马村夫阅读 368评论 0 0