题目地址：

pid=2473">HDU 2473

这题曾经碰到过，没做出来。

。如今又做了做，还是没做出来。

。、、

这题涉及到并查集的删除操作。想到了设一个虚节点，可是我把虚节点设为了要删除的点的父节点。一直是栈溢出，目測是无限递归了。

看了看别人的做法。 原来仅仅要建一个映射就能够了，虚节点是作为的新的映射，每次删除一个点，就把他映射到一个新的点上去。

代码例如以下：

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

int bin[2100000], _hash[2100000], d[2100000];

int find1(int x)

{

    return bin[x]==d[x]?d[x]:bin[x]=find1(bin[x]);

}

void join(int x, int y)

{

    int f1=find1(x);

    int f2=find1(y);

    if(f1!=f2)

        bin[f2]=f1;

}

int main()

{

    int n, m, i, cnt, num=0, sum, a, b;

    char c;

    while(scanf("%d%d",&n,&m)!=EOF&&n+m)

    {

        num++;

        sum=0;

        cnt=n;

        for(i=0; i<2000000; i++)

        {

            bin[i]=i;

            d[i]=i;

        }

        while(m--)

        {

            getchar();

            scanf("%c",&c);

            if(c=='M')

            {

                scanf("%d%d",&a,&b);

                join(a,b);

            }

            else

            {

                scanf("%d",&a);

                bin[a]=cnt;

                d[a]=cnt++;

            }

        }

        memset(_hash,0,sizeof(_hash));

        for(i=0; i<n; i++)

        {

            a=find1(d[i]);

            if(!_hash[a])

            {

                sum++;

                _hash[a]=1;

            }

            //printf("%d ",a);

        }

        //puts("");

        printf("Case #%d: %d\n",num,sum);

    }

    return 0;

}