本文共 1153 字,大约阅读时间需要 3 分钟。
/* 题意:n个学生(0~n-1),m组,一个学生可以同时加入不同的组。 有一种传染病,如果一个学生被感染,那么和他同组的学生都会被感染。 现已知0号学生被感染,问一共有多少个人被感染。 思路:基本的并查集操作。 首先将每个学生都初始化为一个集合,然后将同组的学生合并, 设置一个数组num[]来记录每个集合中元素的个数,最后只要输出0号学生所在集合中元素的个数即可。*/#includeint num[30005]; //结点所在集合元素的个数int father[30005];void make_set(int x){ //初始化集合 father[x] = x; num[x] = 1;}int find_set(int x){ //查找x元素所在集合, 返回根节点 return x == father[x] ? father[x] : find_set(father[x]);}void union_(int x, int y){ //合并x, y所在的集合 x = find_set(x), y = find_set(y); if(x == y) return ; //同一个集合则不需要合并 if(num[x] < num[y]) { //小集合合并到大集合 father[x] = y; num[y] += num[x]; } else{ father[y] = x; num[x] += num[y]; }}int main(){ int n, m, t, x, y, i, j; while(scanf("%d %d", &n, &m) && (n || m)){ for(i = 0; i < n; i++) make_set(i); for(i = 0; i < m; i++){ scanf("%d", &t); scanf("%d", &x); for(j = 1; j < t; j++){ scanf("%d", &y); union_(x, y); } } printf("%d\n", num[find_set(0)]); } return 0;}
转载地址:http://oikxi.baihongyu.com/