**
** 严重急性呼吸系统综合症(SARS)是一种病因不明的非典型肺炎，在2003年3月中旬被确认为全球威胁。为了尽量减少传染给他人，最好的策略是把嫌疑人和其他人分开。 在不扩散的你的疾病大学(NSYSU)，有许多学生团体.同一组中的学生经常相互交流，一个学生可以加入几个小组。为了防止SARS的可能传播，NSYSU收集所有学生组的成员名单，并在其标准操作过程(SOP)中制定以下规则。 一旦一个组中的一个成员是嫌疑犯，这个组中的所有成员都是嫌疑犯。 然而，他们发现，当学生被认定为嫌疑人时，很难识别出所有的嫌疑人。你的工作是写一个程序找出所有嫌疑人。 输入 输入文件包含几种情况。每个测试用例从一行中的两个整数n和m开始，其中n是学生的数目，m是组的数目。您可以假设0<n<=30000和0<=m<=500。每个学生都由0到n−1之间的唯一整数编号，在所有情况下，最初都将学生0识别为嫌疑犯。这一行后面跟着组的m个成员列表，每组一行。每一行的开头都是一个整数k，表示组中的成员数。在成员数之后，有k个整数代表这个组中的学生。一行中的所有整数至少用一个空格分隔。 N=0和m=0的情况表示输入的结束，不需要处理。 输出量 在每一个案件中，输出一行嫌疑犯的数量。 样本输入 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 样本输出 4 1 1
并查集模板题
#include <cstdio> #include <cstring> #include <algorithm> #include<iostream> using namespace std; int main() { int a[1005]; int n,k,t,i; cin>>t; while(t--) { cin>>n>>k; for(i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+1+n); int minn=a[1]; int s; int sum=0; for(i=2;i<=n;i++) { if(a[i]>k) { break; } else { s=k-a[i]; sum+=s/minn; } } cout<<sum<<endl; } return 0; } #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int n,m; int f[30020],num[30020]; void init() { for(int i=0;i<n;i++) { f[i]=i; num[i]=1; } } int get(int x) { if(f[x]==x) return x; else { f[x]=get(f[x]); return f[x]; } } void merge(int u,int v) { int t1=get(u); int t2=get(v); if(t1!=t2) { f[t1]=t2; num[t2]+=num[t1]; } } int main() { while(~scanf("%d %d",&n,&m)) { if(n==0&&m==0) break; init(); for(int i=0;i<m;i++) { int t,u,v; scanf("%d %d",&t,&u); for(int j=1;j<t;j++) { scanf("%d",&v); merge(u,v); } } int x=get(0); printf("%d\n",num[x]); } return 0; }