并查集（加入、查找、删除）

并查集

----------------------来源洛谷
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数Z i ,X i ,Y i​ 。

当Z i =1 时，将 X i​ 与Y i 所在的集合合并。
当 Z i =2 时，输出 X i​ 与 Y i​ 是否在同一集合内，是的输出 Y 否则输出 N。

输出格式
对于每一个Z i =2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例
输入 #1复制
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出 #1复制
N
Y
N
Y
说明/提示
对于 30% 的数据，N≤10，M≤20 。
对于70% 的数据，N≤100，M≤10^3。
对于 100% 的数据，1≤N≤10^4 ,1≤M≤2×10e5。

ac代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int pre[N];
int find(int x){
	if(pre[x]==x) return x;
	else 
		return pre[x] = find(pre[x]);
}
void join(int x,int y){
	int ff1=find(x);
	int ff2=find(y);
	pre[ff1]=ff2;
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		pre[i]=i;
	}
	while(m--){
		int z,x,y;
//		for(int i=1;i<=n;i++){
//			printf("%d ",pre[i]);
//		}
//		system("pause");
		scanf("%d%d%d",&z,&x,&y);
		if(z==2){
			if(find(x)==find(y)){
				printf("Y\n");
			}
			else
				printf("N\n");
		}
		else{
			join(x,y);
		}
	}
	
	
	
	return 0;
}

Junk-Mail Filter（并查集删除）

--------------------来源HDU - 2473
现在有n个不同的垃圾，要做分组，而你正好是那个无辜的分类操作员，现在给你m个指令

指令M a b 表示让a与b所在的组合并在同一组
指令S a 表示将a独立成一组
一顿操作猛如虎，宝宝心里也很苦，麻烦大家来捣鼓，最后分成多少组

Input
输入包含多组，每组两个整数n，m(1<=n<=100000,1<=m<=1000000)

接下来m行M a b或S a表示操作

当n=m=0时表示结束输入

Output
对于每组数据，等操作结束后，输出分组的个数，具体格式见样例。

Sample Input
5 6
M 0 1
M 1 2
M 1 3
S 1
M 1 2
S 3

3 1
M 1 2

0 0
Sample Output
Case #1: 3
Case #2: 2

ac代码：

#include<iostream>
#include<set>
using namespace std;
const int N = 1250000;
int pre[N];
int n,m,cnt;
int find(int x){
	return x==pre[x]?x:pre[x]=find(pre[x]);
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		pre[fx]=fy;
}
void del(int x){
	pre[x]=cnt;
	pre[cnt]=cnt++;
}
void clear(){
	cnt=n;
	for(int i=0;i<n;i++)
		pre[i]=cnt++;
	for(int i=n;i<2*n;i++)
		pre[i]=i;
}
void debug(){
	for(int i=0;i<n;i++)
		printf("%d %d\n",i,find(i));
	putchar(10);
}
void ress(){
	set<int> s;
	for(int i=0;i<n;i++){
		s.insert(find(i));
	}
	printf("%d\n",s.size());
}
int main()
{
	//freopen("in.txt","r",stdin);
	int title=1;
	while(~scanf("%d%d",&n,&m)){
		getchar();
		if(!n&&!m) return 0;
		clear();
		while(m--){
			char ch;
			scanf("%c",&ch);
			if(ch=='M'){
				int x,y;scanf("%d%d",&x,&y);getchar();
				merge(x,y);
			}
			else{
				int x;scanf("%d",&x);getchar();
				del(x);
			}
		}
		printf("Case #%d: ",title++);
		ress();getchar();
	}
	
	
	return 0;
}