【问题描述】

这个城市的帮派很混乱，随着时间的推移，他们组织不断地变化着。

现在给你一些信息，请你统计最后有多少个帮派。

信息包含下列两种：

1、M x y：编号为x和y的人属于同一帮派

2、S x：某年某月，编号为x的人新组建一个帮派。

信息是按时间顺序给出的。

【输入格式】

第一行包含两个整数：n和m，分别表示帮派的总人数（编号为0…n-1），和m条信息。接下来的m行，每行是一条信息。

【输出格式】

一个整数，表示帮派数量。

【输入样例】

【样例1】
5 6
M 0 1
M 1 2
M 1 3
S 1
M 1 2
S 3

【样例2】
3 1
M 1 2

【输出样例】

【样例1】
3

【样例2】
2

【数据范围】

(1 ≤ N ≤ 10^5 , 1 ≤ M ≤ 10^6)

【来源】

hdu 2473

此题是一个并查集的高级运用。首先我们要明白并查集是不支持真删除的，所我们只能假删除。详解如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=1100005;
int sum[maxn],a[maxn],pa[maxn],n,m,t=1;
//sum【i】是指i为代表的帮派的人数，a【i】为i这个人当前的假名（用于实现假删除）。
int find(int x)
{if(pa[x]==x) return x;pa[x]=find(pa[x]);return pa[x];
}void in()
{memset(sum,0,sizeof(sum));memset(a,0,sizeof(pa));memset(a,0,sizeof(pa));scanf("%d%d",&n,&m);for(int i=0;i<n;i++)pa[i]=i,a[i]=i,sum[i]=1;
}void un(int x,int y)
{if(find(x)==find(y)) return;sum[find(y)]+=sum[find(x)];sum[find(x)]=0;pa[find(x)]=find(y);
}void init()
{for(int i=1;i<=m;i++){char s[5];scanf("%s",s);if(s[0]=='M'){int x,y;scanf("%d%d",&x,&y);un(a[x],a[y]);}if(s[0]=='S'){int x;scanf("%d",&x);sum[find(a[x])]--;//将他从帮派删除后，帮派人数要减一。a[x]=n+t;//给他一个新的假名。t++;pa[a[x]]=a[x];sum[a[x]]=1;}}
}int main()
{in();init();int ans=0;for(int i=0;i<=n+m;i++)if(sum[i]) ans++;printf("%d",ans);return 0;
}