上面那个是优化过的，没看错.......可能数据碰巧不喜欢这样被优化。

这是标准解法。

#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;
}

评论