Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
提供我的代码,仅供参考。In Reply To:并查集老是WA,哪位帮忙看下代码。。 Posted by:yayu_myself at 2009-12-27 10:44:03 //AC, 0ms, G++ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <vector> using namespace std; #define M 30010 int d[M];//disjoint set int n, m; int f(int x) { int r = x; while (d[r] != r) r = d[r]; int t; while (d[x] != r) t = d[x], d[x] = r, x = t; return r; } void u(int x, int y) { x = f(x); y = f(y); if (!x) d[y] = x; else d[x] = y; } bool func() { scanf("%d%d", &n, &m); if (!n && !m) return 0; for (int i = 0; i < n; ++ i) d[i] = i; while (m --) { int k; scanf("%d", &k); if (!k) continue; int n1; scanf("%d", &n1); while (-- k) { int n2; scanf("%d", &n2); u(n2,n1); } } return 1; } int main() { while (func()) { int cnt = 0; for (int i = 0; i < n; ++ i) if (!f(i)) ++ cnt; printf("%d\n", cnt); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator