/////////////////////////////////////////
//作品名称:并查集应用
//作者姓名:满天飞
//作品时间:2008-8-15
//最后修改:2008-8-15
//Q Q 号码:280282813
//版权所有,翻版必究
/////////////////////////////////////////

#include<iostream>
using namespace std;
class Set
{
    private:
        int* ary;
        int length;
    public:
        int Find(int index);
        bool Union(int first, int second);
        Set(int n);
        int Count();
        virtual ~Set(){delete[]ary;}
};
int Set::Count()
{
    int i, ct;
    ct = 0;
    for(i = 1; i <= length; ++i)
    {
        if(ary[i] < 0)
            ct++;
    }
    return ct;
}
Set::Set(int n)
{
    int i;
    ary = new int[n+10];
    length = n;
    for(i = 1; i <= n; ++i)
        ary[i] = -1;

}
//将每次查找过的路线上的结点全部都指向根结点
int Set::Find(int index)
{
    int i, j, t;
    if(index <= 0 || index > length) return -1;

    //查找index元素的根结点
    for(i = index; ary[i] > 0; i = ary[i]);
    //将这条路线上的所有元素全部指向根结点
    for(j = index; j != i; j = t){
        t = ary[j];
        ary[j] = i;
    }
    return i;
}

//树的根结点保存树的元素个数,以负值的形式保存
bool Set::Union(int first, int second)
{
    int i, j;
    if(first <= 0 || first > length)
        return false;
    if(second <= 0 || second > length)
        return false;
    //寻找两个元素所在树的根结点
    i = Find(first);
    j = Find(second);

    //越过边界或者两个元素已经在同一棵树中
    if(i == -1 || j == -1 || i == j)
        return false;

    //如果第i棵树的元素比第j棵树的元素要多则将j加入到i中
    if(ary[i] < ary[j]){
        ary[i] += ary[j];
        ary[j] = i;
    }
    //否则将i加入到j中
    else{
        ary[j] += ary[i];
        ary[i] = j;
    }
    return true;
}
int main(int argv, char* argc[])
{
    int stu, num, ct;
    int i, first, second;
    ct = 1;
    while(1)
    {
        scanf("%d%d", &stu, &num);
 
        if(stu == 0 && num == 0)
            break;
        Set set(stu);
        for(i = 0; i < num; ++i)
        {
            cin>>first>>second;
            set.Union(first, second);
        }
        cout<<"Case "<<ct<<": "<<set.Count()<<endl;
        ct++;
    }
    return 0;
}

评论