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.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.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
題意:找出SARS病毒的可疑攜帶者,0號同學為感染者,所以與0號同學同組的人都為可疑攜帶者
思路:簡單的並查集,找到以0為頭的組,然後求出該組的秩的大小。
#include#include #include #include #include #include #include using namespace std; int uset[30010]; int rank[30010]; void makeset(int n) { memset(uset,0,sizeof(uset)); for(int i=0; i =rank[y]) { uset[y]=x; rank[x]=rank[x]+rank[y]; } else { uset[x]=y; rank[y]=rank[y]+rank[x]; } } int main() { int n,m,k,i,j; int first,next; while(~scanf("%d %d",&n,&m)) { if(n==0&&m==0) break; makeset(n); for(i=0; i