扩展域并查集

开始填坑力

引

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。带路径压缩的并查集的时间复杂度已被证明是 \(O(\alpha(n))\) 的。这个函数的值在当 \(n\) 实际有意义的范围内不会大于 \(4\) 。

但是对于多组关系，普通的并查集就难以维护了。

这个时候就可以使用 扩展域并查集 。

扩展域并查集常用来维护多组关系的集合合并问题，在实现上比带权并查集要简单一些 (个人觉得) 。

主要思想

其实很简单，将一个点拆分成多个点，在不同的关系中使用，维护多个关系。

代码实现时，可以通过的对点的序号 \(+\) 点的总个数来实现拆点操作。

下面看例题：

实际应用

NOIp提高组2010：关押罪犯

题目描述

\(S\) 城现有两座监狱，一共关押着 \(N\) 名罪犯，编号分别为 \(1- N\) 。

他们之间的关系自然也极不和谐。

很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。

我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。

如果两名怨气值为 \(c\) 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 \(c\) 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力 从大到小 排成一个列表，然后上报到 \(S\) 城 \(Z\) 市长那里。

公务繁忙的 \(Z\) 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 \(N\) 名罪犯间的矛盾关系后，警察局长觉得压力巨大。

他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。

假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使 \(Z\) 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

第一行为两个正整数 \(N\) 和 \(M\) ，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的 \(M\) 行每行为三个正整数 \(a_j,b_j,c_j\) ，表示 \(a_j\) 号和 \(b_j\) 号罪犯之间存在仇恨，其怨气值为 \(c_j\) 。

数据保证 \(1≤aj<bj<N,0<cj≤1000000000\) 且每对罪犯组合只出现一次。

输出格式

输出共 \(1\) 行，为 \(Z\) 市长看到的那个冲突事件的影响力。

如果本年内监狱中未发生任何冲突事件，请输出 \(0\) 。

数据范围

\(N\leq 20000,M \leq 100000,\ 1≤aj<bj<N,\ 0<cj≤1000000000\)

样例

in:

out:

例题解析：

题目求最大影响的最小值，由贪心我们可以可以知道，我们要尽量不让更大的冲突发生，考虑排序，先保证让大的冲突不发生。

若是只有一个监狱，那就直接使用一个普通并查集，维护就好。然而此题有两个监狱，一个人放在这个监狱，另一个人必定放在另外一个监狱里面。

我们可以考虑把第 \(i\) 个人拆成 \(i\) 和 \(i+1\) 。一个维护友好的集合，一个维护对立的集合。每次查询一个关系，两人应该分别在两个集合中，若查询到两个人在同一集合，则这个事件无法避免的会发生。

放code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1000010;

struct iee
{
	int x,y;
	ll k;
} rela[N];
bool cmp(iee a,iee b)
{
	return a.k>b.k;
}

int n,m;
int parent[N];
void init();
int find(int x);
int union_(int x,int y);
int check(int x,int y);

int main()
{
	init();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%lld",&rela[i].x,&rela[i].y,&rela[i].k);
	sort(rela+1,rela+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		if(check(rela[i].x,rela[i].y))
		{
			cout<<rela[i].k;
			exit(0);//贪心，若在同一集合直接输出并退出
		}
		else
		{
			union_(rela[i].x+n,rela[i].y);
			union_(rela[i].x,rela[i].y+n);//扩展域并查集核心：x + n
		}
	}
	cout<<0;
	return 0;
}

void init()
{
	for(int i=0;i<N;i++)
		parent[i]=i;
}

int find(int x)
{
	int x_root=x;
	while(x_root!=parent[x_root])
	{
		x_root=parent[x_root];
	}
	while(x!=x_root)
	{
		int tmp=parent[x];
		parent[x]=x_root;
		x=tmp;
	}
	return x_root;
}

int union_(int x,int y)
{
	int x_root=find(x);
	int y_root=find(y);
	if(x_root==y_root) return 0;//合并失败
	parent[x_root]=y_root;
	return 1;
}

int check(int x,int y)
{
	return find(x)==find(y);
}

扩展域并查集

引