2045607 2006-08-27 22:32:59 Accepted 1789 C++ 00:00.02 668K St.Crux 2045606 2006-08-27 22:32:16 Accepted 1789 C++ 00:00.02 556K St.Crux 上面那个是优化过的，没看错.......可能数据碰巧不喜欢这样被优化。 这是标准解法。 #include <cstdio>#include <string> int p[30001], r[30001], n, m, t, x, y, ans; int findset(int i){ if(i == -1 || i >= n)  return -1; if(p[i] != -1 && p[i] != i)  p[i] = findset(p[i]); return p[i];} int ufs(int a, int b){ a = findset(a); b = findset(b); if(a == b) return a; if(a == -1) return b; if(b == -1) return a; if(r[a] < r[b]) {  p[a] = b;  return b; } else  {  if(r[a] == r[b]) r[a] ++;  p[b] = a;  return a; }} void init(){ memset(r, 0, sizeof(r)); int i; for(i = 0; i < n; i ++) {  p[i] = -1; }} int main(){ //freopen("in.txt", "r", stdin); while(scanf("%d %d", &n, &m) && n) {  int i, k;  init();  for(i = 0; i < m; i ++)  {   scanf("%d", &t);   scanf("%d", &x);   if(p[x] == -1)    p[x] = x;   for(k = 1; k < t; k ++)   {    scanf("%d", &y);    if(p[y] == -1)     p[y] = y;    ufs(x, y);   }  }  ans = 1;  if(p[0] != -1)  {   for(i = 1; i < n; i ++)   {    if(findset(i) == findset(0))     ans ++;   }  }  //pt();  printf("%d\n", ans); } return 0;} 在WrongAnswer一个多钟头以及顺便看完了PLU的SC总决赛后，换了种简单的写法，AC了。并且找到了原来的错误。 #include <cstdio>#include <string> int p[30001], n, m, t, x, y, ans; int findset(int i){ if(p[i] != i)  p[i] = findset(p[i]); return p[i];} void init(){ int i; for(i = 0; i < n; i ++) {  p[i] = i; }} int main(){ //freopen("in.txt", "r", stdin); while(scanf("%d %d", &n, &m) && n) {  int i, k;  init();  for(i = 0; i < m; i ++)  {   scanf("%d", &t);   scanf("%d", &x);   x = findset(x);   for(k = 1; k < t; k ++)   {    scanf("%d", &y);        if(x != findset(y))     p[findset(y)] = x;   }  }  ans = 1;    for(i = 1; i < n; i ++)  {   if(findset(i) == findset(0))    ans ++;  }  //pt();  printf("%d\n", ans); } return 0;}

评论