加强版   啊  ，看了都不敢做了   。后来先做了食物链这个我还是看过的。但还是A不掉，没明确神魔意思 。总而言之。大牛的博客是个好东西。我就那么看了一下，还是不懂怎莫办啊，哎，就那样就A掉了。

。。。

。

。。

今天我们来谈一下这个并查集的删除操作，依据我对大牛的理解啊，这个并查集的删除操作并非把原来的节点删除掉，而是用一个替身替掉，如今的这个点仅仅是用作桥梁的作用，即是没用的，del  ，，，del  ，。。。删除，那些被删掉的就从n開始给他们一个地址，然后即例如以下代码所看到的

比方说如上图。还没有并到5之前，要删除节点4。假设直接把4直接删除掉的话，那么4上的关系所有删除了。1,3就不在一个集合，可是还要他们在一个集合。那么就给4一个虚拟的节点，在接下来把虚拟节点就是1,3的父节点了，可是这样并非正确的，那么就在和5并起来的时候，把它们各自的虚拟节点并上去 。由于初始化的时候他们的虚拟节点也是他们本身。所以它们最后还是并到了一个集合。根节点还是5.有可能也是虚拟的节点。这都不重要，可是1,3的关系没有变。

假如已经变为上面的那个图了。把4删除掉之后。给他一个新的虚拟节点之后。可是他本身还在这边，相当于一个一个桥连接着。仅仅是他的父节点已经变了。可是其它的还在这里面。

也就是说已经成功的把它删除了，他已经属于还有一个集合了

下面是測试数据

5 6

M 0 1

M 1 2

M 1 3

S 1

M 1 2

S 3

#include <stdio.h>

#include <string.h>

#define N 100001

#define M 1000001

int par[N+M+50];

int repplace[N+50];

int flag[N+M];

int ind;

void  init(int n )

{

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

  {

    par[i]=i;

    repplace[i]=i;

  }

  ind =n;

}

int findset(int n)

{

	if(n==par[n])

		return n;

	else

        return par[n]=findset(par[n]);

}

void  unite(int n,int m)

{

	int pn=findset(n);

	int pm=findset(m);

	if(pn!=pm)

		par[pn]=pm;

}

void Delete(int n)//删除操作。

{

	repplace[n]=ind;

	par[ind]=ind;

	ind++;

}

int main()

{

	int a,b;

	char s[3];

	int x,y;

	int cas=0;

	while(scanf("%d%d",&a,&b)==2)//我一直纠结为什莫会WA。推断输入的控制条件错了

	{

	    if(a==0&&b==0)

            break;

		init(a);

        for(int i=0;i<b;i++)

        {

        	scanf("%s",s);

        	if(s[0]=='M')

        	{

               scanf("%d%d",&x,&y);

               unite(repplace[x],repplace[y]);

        	}

        	else

        	{

               scanf("%d",&x);

               Delete(x);

        	}

        }

        memset(flag,0,sizeof(flag));

        int ans=0;

        for(int i=0;i<a;i++)//推断他们有几个集合

        {

              int hh=findset(repplace[i]);

              if(!flag[hh])

              {

                 flag[hh]=1;

                 ans++;

              }

        }

         printf("Case #%d: %d\n",++cas,ans);

	}

}

其他就不做介绍了，仅仅要会并查集的一般能看懂看懂。看不懂可评论。或发私信。。。

。

。。