警察抓贩毒集团。有不同类型的犯罪集团，人员可能重复，集团内的人会相互接触。现在警察在其中一人（0号）身上搜出毒品，认为与这个人直接接触或通过其他人有间接接触的人都是嫌疑犯。问包括0号犯人共有多少嫌疑犯？
Input
多样例输入。 每个测试用例以两个整数n和m开头，其中n为人数，m为犯罪集团数。你可以假定0 < n <= 30000和0 <= m <= 500。在所有的情况下，每个人都有自己独特的整数编号0到n−1, 且0号是公认的嫌疑犯。 接下来m行输入，每个犯罪集团一行。每一行从一个整数k开始，它本身表示集团内成员的数量。按照成员的数量，在这个组中有k个整数表示人员。一行中的所有整数都被至少一个空格隔开。 n = 0且m = 0时输入结束。
Output
对于每个样例，输出嫌疑犯人数。
思路：基础并查集，合并后看有多少人与0号在同一个集合中就行了。
#include<ctime> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 const int maxn = 3e4 + 10; const int inf = 0x3f3f3f3f; int pre[maxn]; void init(int n) { for(int i = 0; i <= n; ++i) pre[i] = i; } int Find(int x) { int r = x; while(r != pre[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 a = Find(x); int b = Find(y); if(a != b) pre[a] = b; } int main() { int n, m; while(~scanf("%d%d", &n, &m) && n + m) { init(n); for(int i = 1; i <= m; ++i) { int k; scanf("%d", &k); int last; for(int j = 1; j <= k; ++j) { int x; scanf("%d", &x); if(j > 1)//两两合并 { join(last, x); } last = x; } } int ans = 1; for(int i = 1; i < n; ++i) { if(Find(i) == Find(0)) ++ans; } printf("%d\n", ans); } return 0; }
