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
題意:有很多組學生,其中0是攜帶者,那麼和攜帶者一組的人都是攜帶者,問有多少個攜帶者?
解題思路:並查集;
參考代碼:
#include#include using namespace std; int father[30000+1],rank[30000+1]; void init(int n){ for (int i=0;i<=n;i++){ father[i]=i; rank[i]=1; } } int find(int x){ if (x!=father[x]) father[x] = find(father[x]); //路徑壓縮 return father[x]; } void Union(int x,int y){ int i=find(x); int j=find(y); if (i==j) return; if (rank[i] >n>>m){ if (n==0&&m==0) break; if (m==0){ cout<<1< >k; if (k==0) continue; int first,second; cin>>first; if (k==1){ Union(first,first); continue; } for (int j=1;j >second; Union(first,second); } } int count=0; for (int i=0;i