原創 The Suspects Time Limit: 1000MS Memory Limit: 20000K Total Submissions: 48698 Accepted: 23286 Description Severe acute respiratory syndrome (SARS), ...
原創
The Suspects
Time Limit: 1000MS Memory Limit: 20000K
Total Submissions: 48698 Accepted: 23286
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 此題出自POJ——1611：http://poj.org/problem?id=1611題目大意： 學校要找出患了SARS一共有多少人，n個學生人數（編號0~n-1），m個協會，每個協會有k個人，並給出這k個人的編號。 每個學生可以參加多個協會，如果一個協會裡面存在1個或多個患病學生，則協會全部人都會患病，所以患病協會裡面可能 存在參加多個協會的患病學生，這樣會帶來協會傳染，學校要求求出患病人數，當然，定義編號為0的學生是首個患病學生。 輸入：第一行n（學生人數）和m（協會數），接下來m行，每行第一個數代表k，接下來k個數代表參加此協會的學生的編號， n==m==0時表示結束。 輸出：患病學生人數 註意：可以輸入多組數據，等結束輸入後再一起分行輸出結果。 解題思路：（並查集演算法具體思路不再贅述，詳情查看：https://www.cnblogs.com/chiweiming/p/9310599.html） 並查集，我們把每個協會的學生的編號整合起來放在同一棵樹上，若一個學生參加了多個協會，則他所參協會的多棵樹會被合併起來成為一棵，這樣最後只需要找出編號為0的學生所在的樹的結點數就是患病學生的人數了。 值得註意的是，代碼中對尋找根節點的演算法進行了優化！ 原來只是單純的尋找某個結點所在樹的根節點，並沒有改變數的結構：
return node==student[node]?node:find_Father(student[node]);
優化後，改變了樹的結構，將結點至根節點的鏈上的所有結點直接指向了根節點，大大方便了下次再次搜尋的效率！
static int find_Father(int node) { //尋找根節點 /* return node==student[node]?node:find_Father(student[node]); */ if(node!=student[node]) { student[node]=find_Father(student[node]); //狀態壓縮，將結點node到根節點這條鏈上的結點直接指向根節點，優化下次尋找根節點的時間 } return student[node]; }
Java代碼：
import java.util.*; public class TheSuspects { static int n; //學生數量 static int m; //組的數量 static int student[]; static int book[]; static int find_Father(int node) { //尋找根節點 /* return node==student[node]?node:find_Father(student[node]); */ if(node!=student[node]) { student[node]=find_Father(student[node]); //狀態壓縮，將結點node到根節點這條鏈上的結點直接指向根節點，優化下次尋找根節點的時間 } return student[node]; } public static void main(String[] args) { Scanner reader=new Scanner(System.in); ArrayList list=new ArrayList(); int count=0; while(reader.hasNext()) { n=reader.nextInt(); m=reader.nextInt(); if(n==0 && m==0) { break; } student=new int[n]; book=new int[n]; for(int i=0;i<n;i++) { student[i]=i; //學生指向自己 book[i]=1; //每個學生為1個結點 } for(int i=1;i<=m;i++) { int k=reader.nextInt(); int node_One=reader.nextInt(); //輸入k個結點中的第一個 for(int j=1;j<=k-1;j++) { int node_Two=reader.nextInt(); int father_One=find_Father(node_One); //找出父節點 int father_Two=find_Father(node_Two); if(father_One!=father_Two) { student[father_Two]=father_One; //合併 book[father_One]+=book[father_Two]; //book[根節點]存儲其所在樹的結點數，每有一個學生加入此數，總結點數+1 } } } list.add(book[find_Father(0)]); //求0所在樹的結點個數 count++; } for(int i=0;i<count;i++) { System.out.println(list.get(i)); } } }
POJ截圖：
23:31:36
2018-07-18
