#include <stdio.h>
#include <algorithm>
using namespace std;
int i,j,n,m,ans;
int const MAXN = 50000;
int uset[MAXN+1];
int Root(int v)
{
    if(uset[v] == v)
        return v;
    uset[v] = Root(uset[v]);
    return uset[v];
}
void Unite(int a,int b)
{	
    uset[uset[b]] = uset[a]; 
}

int main()
{
    int ncase = 1;
    while(scanf("%d%d",&n,&m) && n+m)
    {
        for(i=0; i<=n; i++)
            uset[i] = i;
        for(i=0; i<m; i++)
        {
            scanf("%d%d",&a,&b);
            if(Root(a)!=Root(b))
               Unite(a,b);
        }
        sort(uset+1,uset+n+1);
        ans = 1;
        for(i=2; i<=n; i++)
        {
        //    printf("%d ",uset[i]);
            if(uset[i]!=uset[i-1])
                ans++;
        }
        printf("case %d: %d\n",ncase,ans);   
        ncase++;     
    }    
    return 0;
}   

• 这个……怎么那么像某人的程序 (977) frkstyc 2005-08-04 17:25:47
  • 并查集是你的 (0) sunmoonstar_love 2005-08-04 17:26:17
    • xf的 (0) frkstyc 2005-08-04 17:26:34
      • 恩，但是为什么Wa呢，我换种方法计数就AC，而这个我感觉也对呀 (0) sunmoonstar_love 2005-08-04 17:27:18
        • 不知道怎么改，不过你的用法不对 (0) frkstyc 2005-08-04 17:31:38
          • 哪里不对呢？ (0) sunmoonstar_love 2005-08-04 17:32:56
            • c/c++不是excel，uset[]的内容不会自动变的 (0) frkstyc 2005-08-04 17:34:00
              • 这个就对了，其他的一样 (416) sunmoonstar_love 2005-08-04 17:36:30
                • 我对您pf得一踏糊涂... (466) T3 2005-08-04 17:45:56
                  • 又错了............ (12) c0500448242 2005-08-04 17:47:21
                  • 。。。。。。又猪头了 (12) sunmoonstar_love 2005-08-04 17:59:31
  • 像过头了,我还以为真是他自己写的. (5) T3 2005-08-04 17:46:50
    • 谢谢你了，你写的真好，简单实用 (9) sunmoonstar_love 2005-08-04 18:00:08