首页 > 代码库 > poj1611 The Suspects
poj1611 The Suspects
题意:
n个学生分属m个团体,(0 < n <= 30000 ,0 <= m <= 500) 一个学生可以属于多个团体。一个学生疑似患病,则它所属的整个团体都疑似患病。已知0号学生疑似患病,以及每个团体都由哪些学生构成,求一共多少个学生疑似患病。
Sample Input
100 4 2 1 2 5 10 13 11 12 14 2 0 1 2 99 2 200 2 1 5 5 1 2 3 4 5 1 0 0 0
Sample Output
4 1 1
思路:
并查集。
实现:
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 int par[30005]; 6 int ran[30005]; 7 8 void init(int n) 9 { 10 for (int i = 0; i < n; i++) 11 { 12 ran[i] = 0; 13 par[i] = i; 14 } 15 } 16 17 int find(int x) 18 { 19 if (par[x] == x) 20 return x; 21 return par[x] = find(par[x]); 22 } 23 24 25 void unite(int x, int y) 26 { 27 x = find(x); 28 y = find(y); 29 if (x == y) 30 return; 31 if (ran[x] < ran[y]) 32 par[x] = y; 33 else 34 { 35 par[y] = x; 36 if (ran[x] == ran[y]) 37 ran[x]++; 38 } 39 } 40 41 int n, m, p, x, y; 42 int main() 43 { 44 while (cin >> n >> m, n || m) 45 { 46 init(n + 1); 47 for (int i = 0; i < m; i++) 48 { 49 scanf("%d", &p); 50 if (!p) 51 continue; 52 scanf("%d", &x); 53 for (int j = 0; j < p - 1; j++) 54 { 55 scanf("%d", &y); 56 unite(x, y); 57 } 58 } 59 int tmp = find(0); 60 int cnt = 0; 61 for (int j = 0; j < n; j++) 62 { 63 if (find(j) == tmp) //不能写成par[j],因为点j可能还没进行路径压缩,结果不一定正确。 64 cnt++; 65 } 66 printf("%d\n", cnt); 67 } 68 return 0; 69 }
poj1611 The Suspects
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。