用Netty实现的简单HTTP服务器
链接:http://poj.org/problem?id=1611
Time Limit: 1000MS | Memory Limit: 20000K | |
Total Submissions: 20031 | Accepted: 9730 |
Description
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
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.
Output
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
The Submitted Code:
#include <iostream> #include <cstdio> #include <cstdlib> #define MAXN 30005 using namespace std; int father[MAXN], N[MAXN]; void Make_Set(int n) { for(int i=0; i<n; i++) { father[i] = i; //使用本身做根;每一个成员开始的父亲节点都为自身; N[i] = 1; } } int Find_Set(int x) { if(x != father[x]) { //合并后树的根是不变的; father[x] = Find_Set(father[x]); } return father[x]; } void Union_Set(int x, int y) { x = Find_Set (x); y = Find_Set (y); if(x == y) return ; if(N[x] > N[y]) { father[y] = x; N[x] += N[y]; } else { father[x] = y; N[y] += N[x]; } } int main() { int n, m; while(~scanf("%d %d", &n, &m) && n || m) { Make_Set(n); for(int i=0; i<m; i++) { int Md, first, ME; scanf("%d %d", &Md, &first); for(int j=1; j<Md; j++) { scanf("%d", &ME); Union_Set(first, ME); //对属于同一个小组的成员集合进行合并; } } printf("%d\n", N[Find_Set(0)]); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。