并查集略解

并查集 是一种十分简单的数据结构，支持以下操作：

1. 将两个集合合并；
2. 查询两个元素是否属于同一个集合。

初始状态下，每个元素各自为一个集合。

下面我们尝试实现这个算法。

我们有四个元素，初始状态下各自为一个集合。

现在我们合并1，2元素。不妨认为把2加入到1所属的集合中，我们连一条边。

下次我们访问2元素的时候，检索到2指向1，我们就能知道12属于同一个集合。注意到，我们指定一个元素作为一个集合的代表，这个代表不会有指向另一个元素的边。判断两个元素是否属于同一个集合的方法就是判断两个元素属于的集合的代表是否是同一个元素。

现在我们将3加入到1，2所属的集合中。同理，我们得到

下次我们访问3的时候，我们会先找到3指向的元素2，再找到2指向的元素1。因为不用支持分开集合的操作，所以为了防止每次都线性遍历一边这个“链”，我们可以合并链，让集合里的每个元素都直接指向这个集合的代表。

至此，我们就实现了并查集。

例

实现文章开头提出的两个操作。

#include 
#include 
#include 

const int MAXN=10010;

int n, m;
//元素指向的元素
int fa[MAXN];
int s1, s2, s3;

int findfa (int x){
	//找到了集合的代表元素
	if (x==fa[x]) return x;
	//继续向前寻找，并压缩路径
	return fa[x]=findfa (fa[x]);
}
int main (){
	scanf ("%d%d", &n, &m);
	//初始状态下，每个元素各形成一个集合。因此，每个元素属于的集合的代表就是他自己
	for (int i=1; i<=n; ++i)
		fa[i]=i;
	for (int i=1; i<=m; ++i){
		scanf ("%d%d%d", &s1, &s2, &s3);
		if (1==s1)
			fa[findfa (s2)]=findfa (s3);
		else
			puts ((findfa (s2)==findfa (s3))?"Y":"N");
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

习题1 luogu P1955 [NOI2015] 程序自动分析

给出关于 $x_1,x_2,...$ 的多个命题，每个命题为 $x_i==x_j$ 或 $x_i!=x_j$。问是否存在一组 $x_1,x_2,...$，使得所有命题都成立。

本题的关键在于判断不等命题是否成立。不等条件较难判断，不妨先使得相等命题尽量成立，然后再判断不等命题是否成立。

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN=1000010;

int T, n;

inline int read (){
	int x=0; char c;
	do c=getchar (); while ('0'>c||'9'=c)
		x=x*10+c-48, c=getchar ();
	return x;
}
struct oper{
	int i, j, t;
	oper(){
		i=j=t=0;
	}
	void input (){
		i=read (); j=read (); t=read ();
	}
}op[MAXN];
//用于离散化的类，若1==id2则这个数来自op[id1].i，否则来自op[id1].j
struct number{
	int d, id1, id2;
	number(){
		d=id1=id2=0;
	}
}num[MAXN*2];
int len;
bool operator< (const number a, const number b){
	return a.d