本文出自:
题意: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, groupint 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\n", sum); } return 0;}
解法二:
#include#include using namespace std;int stu[30001];int total[30001];//the num of stu, groupint 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\n", total[getParent(0)]); //不能直接stu[0],由于stu[0]不一定是根节点。 } return 0;}