一道非常简单的并查集题目,只需要把每组人均合并到一起。最后统计和 0 是一个父亲的数量即可,20 分钟 Accepted.
/* POJ 1611 * By Ceeji * Union */ #include <iostream> #include <cstring> using namespace std; #define MAX_N 30000 int m, n; int father[MAX_N]; int get_father(const int p) { if (father[p] == -1 || father[p] == p) { father[p] = p; return p; } father[p] = get_father(father[p]); return father[p]; } void set_union (const int x, const int y) { int fx = get_father (x); int fy = get_father (y); father[fx] = fy; } void do_work () { for (int i = 0; i < MAX_N; ++i) father[i] = -1; for (int j = 0; j < m; ++j) { int gn, tmp, first; cin >> gn >> first; for (int i = 0; i < gn - 1; ++i) { cin >> tmp; if (get_father(tmp) != get_father(first)) set_union (tmp, first); } } int f = get_father(0); int num = 0; for (int i = 0; i < n; ++i) { if (get_father(i) == f) ++num; } cout << num << endl; } int main () { while (true) { cin >> n >> m; if (m == 0 && n == 0) return 0; do_work (); } return 0; } |