首页 > 代码库 > 感冒病毒
感冒病毒
20170211感冒病毒 |
难度级别:B; 运行时间限制:1000ms; 运行空间限制:51200KB; 代码长度限制:2000000B |
试题描述 |
一种感冒病毒正在学校里传播,这所学校有n个学生,m个学生社团,每个学生可能参加了多个社团,因为同一个社团的学生交流较多,所以如果一个学生感染上感冒病毒,那么他所在的社团里的所有学生都会感染上感冒病毒,现在已知0号学生感染上感冒病毒,问现在有多少人会感染上感冒病毒。 |
输入 |
输入的第一行是两个整数 n 和 m,表示学生的数目和社团的数目,学生的编号为 0 到 n-1。 接下来m行,每行首先是一个数ki,表示这个社团有ki个人,接下来ki个整数,表示这个社团里每个学生的编号aij。 |
输出 |
输出为一行,包含一个整数。表示感染感冒病毒的人数。 |
输入示例 |
100 4 2 1 10 5 10 13 11 12 14 2 0 1 2 9 2 |
输出示例 |
7 |
其他说明 |
数据范围:3<=n<=30000,3<=m<=500,1<=ki<=n,0<=aij<n。 |
这是一道关于父亲和祖宗的问题。我们要找到真正的祖宗(父亲的祖宗)而不是父亲。 1 #include <iostream> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <algorithm> 7 using namespace std; 8 int fa[30101]; 9 int find(int x) //寻找根 10 {11 if(fa[x]==x) return x;12 return fa[x]=find(fa[x]);13 }14 int main()15 {16 int n,m;17 scanf("%d%d",&n,&m);18 for(int i=0;i<n;i++) fa[i]=i; //初始化:根都是自己 19 for(int i=1;i<=m;i++)20 {21 int z,first,s;22 scanf("%d%d",&z,&first); //first是第一个数,当成本社团后面所有人的根 23 for(int j=1;j<z;j++)24 {25 scanf("%d",&s);26 fa[find(s)]=fa[find(first)]; //找到first的根,并更新本社团其他人的根 27 }28 }29 int ans=0,w=find(0); //找到0的根 30 for(int i=0;i<n;i++)31 {32 if(fa[find(i)]==w) ans++; //所有和0的根相同的,都会被感染 33 }34 printf("%d",ans);35 return 0;36 }
|
感冒病毒
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。