题目链接
http://poj.org/problem?id=1611
题意
给出 n, m
有n个人 编号为 0 - n - 1 有m组人 他们之间是有关系的
编号为 0 的人是 有嫌疑的 然后和 编号为0的人有关系 或者 和 编号为0的人有关系的人 有关系的 都是有嫌疑的
找出共有多少人有嫌疑
思路 将所有有关系的人 合并 然后 去查找 所有的人的根节点 如果和编号为0的人的根节点 相同 他就是有关系的
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 5e4 + 10; const int MOD = 1e9 + 7; int pre[maxn]; int find(int x) { int r = x; while (pre[r] != r) r = pre[r]; int i = x, j; while (i != r) { j = pre[i]; pre[i] = r; i = j; } return r; } void join(int x, int y) { int fx = find(x), fy = find(y); if (x != fy) pre[fx] = fy; } void init() { for (int i = 0; i < maxn; i++) pre[i] = i; } int main() { int n, m; while (scanf("%d%d", &n, &m) && (n || m)) { init(); int Max = -INF; for (int i = 0; i < m; i++) { int k; int ini, num; scanf("%d%d", &k, &ini); Max = max(Max, ini); for (int i = 1; i < k; i++) { scanf("%d", &num); Max = max(num, Max); join(ini, num); } } int ans = 1; int vis = find(0); for (int i = 1; i <= Max; i++) { if (find(i) == vis) ans++; } cout << ans << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433109.html
相关资源：JAVA上百实例源码以及开源项目