Junk-Mail Filter-并查集

HDUOJ.2473 Junk-Mail Filter
题解参考

题目大意

共对n个元素进行m次操作，操作共有两种，M a b为定义a与b为同一类元素，S a定义为将a节点与其他节点分离；
输出共有几类元素；

思路

我们可以将元素用代表元代替：
每一次该元素被分离是，就给它定义一个新的代表元，并定义该代表元的根为其自己；
同时，对于旧的树状结构，下级元素的根依然为该元素的旧代表元，所以不会影响旧关系的传递；

这样就可以将不同的关系之间分离开，不会互相干扰；

代码

#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;

const int N = 1e5 + 5;
int rep[N];
int fa[1100006];//Nmax+Mmax
int fg[1100006];
int find(int x)
{
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
int main()
{
    int n,m,a,b,faa,fbb,ccs=1,crep;
    char o;
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        crep=n+1;
        for(int i=0;i<n;i++)//初始化
        {
            rep[i]=i;
            fa[i]=i;
        }
        for(int i=0;i<m;i++)
        {
            cin>>o;
            if(o=='M')
            {
                scanf("%d%d",&a,&b);
                faa=find(rep[a]);
                fbb=find(rep[b]);
                if(faa!=fbb)//操作代表元
                {
                    fa[faa]=fbb;
                }  
            }
            else if(o=='S')
            {
                scanf("%d",&a);
                rep[a]=crep;//更新代表元
                fa[crep]=crep;
                crep++;
            }
        }
        int ans=0;
        memset(fg,0,sizeof fg);
        for(int i=0;i<n;i++)
        {
            if(!fg[find(rep[i])])//fg标记该集合是否统计过
            {
                fg[find(rep[i])]=1;
                ans++;
            }
        }
        printf("Case #%d: %d\n",ccs++,ans);
    }
    return 0;
}