「NOIP模拟赛」感冒病毒
「题目描述」
一种感冒病毒正在学校里传播，这所学校有n个学生，m个学生社团，每个学生可能参加了多个社团，因为同一个社团的学生交流较多，所以如果一个学生感染上感冒病毒，那么他所在的社团里的所有学生都会感染上感冒病毒，现在已知0号学生感染上感冒病毒，问现在有多少人会感染上感冒病毒。
「输入」
输入文件：suspects.in
输入的第一行是两个整数n和m，表示学生的数目和社团的数目,学生的编号为0到n-1。
接下来m行，每行首先是一个数ki，表示这个社团有ki个人，接下来ki个整数，表示这个社团里每个学生的编号aij。
「输出」
输出文件：suspects.out
输出为一行，包含一个整数。表示感染感冒病毒的人数。
「输入样例」
100 4
2 1 10
5 10 13 11 12 14
2 0 1
2 9 2
「输出样例」
7
「数据范围」
对于100%的数据，3<=n<=30000
对于100%的数据，3<=m<=500
对于100%的数据，1<=ki<=n
对于100%的数据，0<=aij<n。
并查集。。。或者建个图搜索神马的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans; int fa[50005]; bool mark[50005]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { //freopen("suspects.in","r",stdin); //freopen("suspects.out","w",stdout); n=read();m=read(); for(int i=0;i<=n+m;i++)fa[i]=i; mark[0]=1; for(int i=n+1;i<=n+m;i++) { int x=read(); while(x--) { int a=read(); int p=find(i),q=find(a); if(mark[p])mark[q]=1; fa[p]=q; } } for(int i=0;i<=n;i++) if(mark[find(i)])ans++; printf("%d",ans); return 0; } |
Subscribe
计数器 9855396
OI 课件=>
OI 课件=>