「NOIP模拟赛」感冒病毒

2014年11月4日2,6240

「题目描述」

一种感冒病毒正在学校里传播,这所学校有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。

并查集。。。或者建个图搜索神马的

 

avatar
  Subscribe  
提醒