并查集笔记

基础知识

基本操作

// 初始化
void init(){
	for(int i = 1; i <= n; i++)
		p[i] = i;
}
// 查询（路径压缩）
int find(int x){
	return x == p[x] ? x : (p[x] = find(p[x]));
}
// 普通合并
void union(int x, int y){
	int fx = find(x), fy = find(y);
	if(fx != fy) p[fx] = fy;
}

启发式合并

  • 由于合并时希望操作元素尽量少，就让少的往大的合并，这就是启发式合并
  • \(n\) 个元素和 \(m\) 次查询，时间复杂度为 \(O(mlogn)\)
// 启发式合并
void union(int x, int y){
    int fx = find(x), fy = find(y);
    if(fx == fy) return;
    if(sz[fx] > sz[fy])
        swap(fx, fy);
    p[fx] = fy;
    sz[fy] += sz[fx];
}

按深度合并

  • 每次合并将深度小的一方合并到深度大的一方
  • 路经压缩时，可能破坏深度值，复杂度不变差
// 按深度合并
void union(int x, int y){
    int fx = find(x), fy = find(y);
    if(fx == fy) return;
    if(dep[fx] > dep[fy])
        swap(fx, fy);
    p[fx] = fy;
    if(dep[fx] == dep[fy])  // 只有深度相等才更新
        dep[fy]++;
}

时间复杂度

  • 启发式合并和深度合并，\(n\) 个元素和 \(m\) 次查询，时间复杂度为 \(O(mlogn)\)
  • 一般来说并查集时间复杂度为 \(O(m*\alpha (m, n))\)。其中 \(\alpha\) 为阿克曼函数的反函数，可以认为是一个小常数
  • 无启发式合并，只路径压缩最坏时间复杂度为 \(O(mlogn)\)，平均复杂度为 \(O*\alpha(m,n)\)。
  • 可以直接认为 \(O(m)\)

带权并查集

int d[N], p[N];
void find(int x){
    if(x == p[x]) return;
    int root = find(p[x]);
    d[x] += d[p[x]];
    p[x] = root;
    return p[x];
}

习题

带权并查集 + 背包DP

POJ1417

题意

一个村庄有两类人，好人坏人， 好人总是说真话， 坏人总是说假话， 给你n个询问和好人、坏人的数量p q， 每个询问 x y yes/no, 表示 x 说 y 是 好/坏人。问是否能够唯一确定哪些是好人， 哪些是坏人， 如果可以输出好人的序号以"end"结尾， 否则输出"no"
补充：

  1. 首先这题我们是知道好人和坏人的各自数量，
  2. 其次题目中可能会形成若干个集合（表示不是连通的一个图）
  3. 每个集合中的好人和坏人都是相对关系无法确定

思路：

见代码注释

Solution

#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
//#include
#include
typedef long long ll;
typedef std::pair PII;
typedef std::pair PLL;
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 710;
int p[N], w0[N], w1[N], n, m, good, bad, d[N];
int f[N][N], fa[N];
bool st[N];
// dp + 并查集
// 根据yes或者no可以将每个小集合内部分两类（但不知道是好是坏）
// 问题转化为->如何从每个小集合中选取适当的数，使得最后有唯一方案（背包DP）
// f[i][j] = 前 i 个集合好人数为 j 的方案数，判断是否为1，然后朴素方案转移即可
void init(){
	memset(st, false, sizeof st);
	memset(f, 0, sizeof f);
	for(int i = 1; i <= n; i++)
		p[i] = i, w0[i] = w1[i] = d[i] = fa[i] = 0;
}

int find(int x){
	if(x == p[x]) return x;
	int root = find(p[x]);
	d[x] ^= d[p[x]];
	p[x] = root;
	return p[x];
}

void Union(int x, int y, int k){
	int fx = find(x), fy = find(y);
	if(fx != fy){
		p[fx] = fy;
		d[fx] = d[y] ^ k ^ d[x];	// 左边一定是 fx
	} 
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	while(cin >> m >> good >> bad, m || good || bad){
		n = good + bad;
		init();
		while(m--){
			int x, y;
			string t;
			cin >> x >> y >> t;
			int k = t == "yes" ? 0 : 1;
			Union(x, y, k);
		}
		int num = 1;
		for(int i = 1; i <= n; i++){
			if(!st[i]){
				int pi = find(i);
				for(int j = i; j <= n; j++)
					if(!st[j] && find(j) == pi){
						st[j] = true;
						d[j] == 0 ? w0[num]++ : w1[num] ++;
					}
				fa[num] = pi;
				num++;
			}
		}
		num--;
		f[0][0] = 1;
		for(int i = 1; i <= num; i++){
			int min_ = min(w0[i], w1[i]);
			for(int j = good; j >= min_; j--){
				f[i][j] += f[i - 1][j - w0[i]];
				f[i][j] += f[i - 1][j - w1[i]];
			}
		}
		if(f[num][good] != 1){
			cout << "no\n";
			continue;
		}
		int now = good;
		vector ans;
		for(int i = num; i >= 1; i--){
			if(f[i - 1][now - w0[i]]){
				for(int j = 1; j <= n; j++){
					if(find(j) == fa[i] && !d[j]){
						ans.pb(j);
					}
				}
				now -= w0[i];
			}
			else{
				for(int j = 1; j <= n; j++)
					if(find(j) == fa[i] && d[j])
						ans.pb(j);
				now -= w1[i];
			}
		}
		sort(ans.begin(), ans.end());
		for(int i = 0; i < ans.size(); i++)
			cout << ans[i] << endl;
		cout << "end\n";
	}
    return 0;
}

贪心+并查集加速

题意

超市里有 \(N\) 个商品. 第 \(i\) 个商品必须在保质期(第 \(d_i\)天)之前卖掉, 若卖掉可让超市获得 \(p_i\) 的利润.
每天只能卖一个商品.
现在你要让超市获得最大的利润.

思路

  • 对价格排序，贪心从高往低选，标记使用了的时间，有冲突就找下一个没有冲突的时间点。
  • 找下一个没有冲突的时间点就是个并查集加速的过程

Solution

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long ll;
typedef std::pair PII;
typedef std::pair PLL;
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 10010;
int p[N], n;
PII item[N];

// 贪心选取，再用并查集加速

int find(int x){
	if(p[x] == -1) return x;
	return p[x] = find(p[x]);
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	while(cin >> n){
		memset(p, -1, sizeof p);
		for(int i = 1; i <= n; i++)
			cin >> item[i].x >> item[i].y;
		sort(item + 1, item + n + 1);
		ll sum = 0;
		for(int i = n; i >= 1; i--){
			int t = find(item[i].y);
			if(t > 0){
				sum += item[i].x;
				p[t] = t - 1;
			}
		}
		cout << sum << endl;
	}
    return 0;
}

带权并查集维护曼哈顿距离，离线执行

题意

有 \(n\) 个网格状的农田，每个农田之间有距离，会依次给出关系，在给出关系后询问两个农田之间的曼哈顿距离是多少？

若无法判断则输出 \(-1\) 。

思路

  • 对于曼哈顿距离的维护，可以开两个数组记录横纵坐标
  • 询问按时间排序后，输出时还原原来的顺序

Solution

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long ll;
typedef std::pair PII;
typedef std::pair PLL;
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 40010;
int n, m, p[N], dx[N], dy[N];

// 带权并查集，对于曼哈顿距离的维护，可以开两个数组记录横纵坐标，不要仅局限于一个数组
// 询问按时间排序后，输出时还需要还原原来的顺序，这点容易被忽略，希望能够记住

void init(){
	for(int i = 1; i <= n; i++)
		p[i] = i, dx[i] = 0, dy[i] = 0;
}

int find(int x){
	if(x == p[x]) return x;
	int root = find(p[x]);
	dx[x] += dx[p[x]], dy[x] += dy[p[x]];
	p[x] = root;
	return p[x];
}

void Union(int x, int y, PII dist){
	int fx = find(x), fy = find(y);
	if(fx == fy) return;
	p[fx] = fy;
	dx[fx] = dx[y] - dx[x] + dist.x;
	dy[fx] = dy[y] - dy[x] + dist.y;
}

struct Q{
	int a, b, c, id;
	bool operator < (const Q& q)const{
		return c < q.c;
	}
}q[N];

struct O{
	int a, b;
	PII dist;
}op[N];

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	bool fl = false;
	while(cin >> n >> m){
		if(fl)
			cout << endl;
		init();
		for(int i = 1; i <= m; i++){
			int a, b, l, k;
			char dir;
			cin >> a >> b >> l >> dir;		// a在左下
			PII dist;
			if(dir == 'W')
				dist = {0, -l};
			else if(dir == 'E')
				dist = {0, l};
			else if(dir == 'S')
				dist = {-l, 0};
			else
				dist = {l, 0};
			op[i] = {b, a, dist};
		}
		int k;
		cin >> k ;
		for(int i = 1; i <= k; i++){
			int a, b, c;
			cin >> a >> b >> c;
			q[i] = {a, b, c, i - 1};
		}
		sort(q + 1, q + 1 + k);
		int p_ask = 1;
		vector ans(k, 0);
		for(int i = 1; i <= m; i++){
			Union(op[i].a, op[i].b, op[i].dist);
			while(q[p_ask].c <= i && p_ask <= k){
				int a = q[p_ask].a, b = q[p_ask].b;
				int pa = find(a), pb = find(b);
				if(pa == pb){
					ans[q[p_ask].id] = abs(dx[b] - dx[a]) + abs(dy[b] - dy[a]);
				}
				else
					ans[q[p_ask].id] = -1;
				p_ask++;
			}
		}
		for(auto t: ans)
			cout << t << endl;
		fl = true;
	}
    return 0;
}

带权并查集+暴力枚举思想

题意

给了 \(n\) 个小朋友，分成三个组进行石头剪刀布，每个组的小朋友只能出固定的手势。而其中会有裁判可以出任意手势。现在给出了 \(m\) 次对局
每次对局只知道两个人之间的胜负。判断其中是否有唯一的裁判，如果有多个输出Can not determine, 有一个输出对应编号和至少多少行可以判定他是裁判，或者没有裁判。

数据范围： \(1 \leq n\leq 500,\; 0\leq m\leq 2000\)

思路

  • 很容易想到边权 % 3 的并查集来维护三组小朋友。
  • 根据数据范围，考虑暴力枚举哪个人是裁判，除开他参与的对局看是否有矛盾，有矛盾则不是裁判，否则就是。
  • 最后判断裁判个数，如果有唯一裁判，至少多少行判出他是裁判 \(<->\) 判断其他人不是裁判的最大行数(小思维点)

Solution

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long ll;
typedef std::pair PII;
typedef std::pair PLL;
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
const int N = 510, M = 2010;
int n, m, p[N], d[N];

struct Q{
	int a, b, dist;
}q[M];

void init(){
	for(int i = 0; i <= n; i++)
		p[i] = i, d[i] = 0;
}

int find(int x){
	if(x == p[x]) return x;
	int root = find(p[x]);
	d[x] = (d[p[x]] + d[x]) % 3;
	p[x] = root;
	return p[x];
}

bool check(int a, int b, int dist){
	int pa = find(a), pb = find(b);
	if(pa == pb){
		if((d[a] - d[b] - dist) % 3)
			return false;
	}
	else{
		p[pa] = pb;
		d[pa] = (d[b] + dist - d[a]) % 3;
	}
	return true;
}

int main(){
	while(scanf("%d%d", &n, &m) == 2){
		init();
		for(int i = 0; i < m; i++){
			int a, b, dist;
			char op;
			scanf("%d%c%d", &a, &op, &b);
			if(op == '<') dist = -1;
			else if(op == '>') dist = 1;
			else dist = 0;
			q[i] = {a, b, dist};
		}
		int cnt = 0, ans = 0, line = 0;
		for(int i = 0; i < n; i++){		// 枚举哪个是裁判
			init();
			bool fl = true;
			for(int j = 0; j < m; j++){
				if(q[j].a == i || q[j].b == i) continue;
				if(!check(q[j].a, q[j].b, q[j].dist)){
					fl = false;
					line = max(line, j);
					break;
				}
			}
			if(fl){
				cnt ++;
				ans = i;
			}
		}
		if(cnt > 1)
			printf("Can not determine\n");
		else if(cnt == 1)
			printf("Player %d can be determined to be the judge after %d lines\n", ans, line + (line != 0));
		else
			printf("Impossible\n");
	}
    return 0;
}
`
算法数据结构并查集

相关

数据结构--栈（C语言实现）

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

牛客练习赛91（并查集+二维偏序+二分）

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

数据结构----单链表升级版

数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

标签