///////////////////////////////////////////作品名称:并查集应用//作者姓名:满天飞//作品时间: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;}

评论