?

题意：0号学生染病，有n个学生，m个小组。和0号学生同组的学生染病，病可以传染。

输入格式：n,m

数量 学生编号1，2,3,4

//m个分组

题解：最为典型的并查集。

解法一：求出所有的集合，然后求出0的parent，把parent为0的parent所有学生求出。

解法二：在计算的过程中统计total；

?

解法一：(一开始用的Vim写的在POJ上交出现 访问禁止错误- - 不知道又神奇的碰上了什么BUG，删了main函数中几个换行符就好了）

?

#include 
  
   
#include 
   
     using namespace std; int stu[30001]; //the num of stu, group int n, m; void init() { for(int i = 0; i < n; i++) stu[i] = i; } int getParent(int a) { if(a == stu[a]) return a; else return stu[a] = getParent(stu[a]); } void Merge(int a, int b) { if(getParent(a) == getParent(b)) return; else stu[getParent(a)] = b; } int main() { int i, j; int deter, sum; int num; int temp1, temp2; while(scanf(%d%d, &n, &m)) { if(n == 0 && m == 0) break; init(); for(i = 0; i < m; i++) { scanf(%d, &num); scanf(%d, &temp1); for(j = 1; j < num; j++) { scanf(%d, &temp2); Merge(temp1, temp2); } } deter = stu[getParent(0)]; sum = 1; for(i = 1; i < n; i++) { if(getParent(i) == deter) sum++; } printf(%d , sum); } return 0; }
   
  

?

?

?

解法二：

?

#include 
  
   
#include 
   
     using namespace std; int stu[30001]; int total[30001]; //the num of stu, group int n, m; void init() { for(int i = 0; i < n; i++) { stu[i] = i; total[i] = 1; } } int getParent(int a) { if(a == stu[a]) return a; else return stu[a] = getParent(stu[a]); } void merge(int a, int b) { if(getParent(a) == getParent(b)) return; else { total[getParent(a)] += total[getParent(b)]; stu[getParent(b)] = a; } } int main() { int i, j; int num;//record the group's num int temp1, temp2; while(scanf(%d%d, &n, &m)) { if(n == 0 && m == 0) break; init(); for(i = 0; i < m; i++) { scanf(%d, &num); scanf(%d, &temp1); for(j = 1; j < num; j++) { scanf(%d, &temp2); merge(temp1, temp2); } } printf(%d , total[getParent(0)]); //不能直接stu[0],因为stu[0]不一定是根节点。 } return 0; } 
   
  

?