并查集之——单链表式并查集

普通并查集（树状）: p[i]表示节点i的父节点，i所在树的根节点是代表元素。

单链表式并查集（单链表状）：时间复杂度 $O(m_{元素值域}+n)$，空间复杂度不同问题不一样。

1、p[i] 表示 i 在单链表形式并查集中的下一个节点。
2、find(x) 表示从 x 向右找第一个没有被用到的 / 染色的元素。

单链表式并查集的应用

经典应用一：修改数组

《修改数组》

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

const int N = 1000010;
int p[N];
int n;

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

int main(){
    scanf("%d", &n);
    for(int i = 1; i < N; i++) p[i] = i;
    for(int i = 1; i <= n; i++){
        int x;
        scanf("%d", &x);
        x = find(x);
        printf("%d%c", x, " \n"[i == n]);
        p[x] = x + 1;
    }
    
    return 0;
}

经典应用二：序列染色问题

《疯狂的馒头》

如果从前向后考虑，后边的染色会覆盖之前的一种染色，可以倒着考虑，如果一段区间已经染色就不再被染色了 (每个位置只会被染色一次) ，然后跳过一些状态，进行优化。

这类题的想通的地方就是 只会出现一次，只会被染色一次

因为p[i] = i表示这个节点 / 物品，还没有出现过，或者还没有被染色过。

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

const int N = 1000010;
int fa[N], ans[N];
int n, m, p, q;

int find(int x){
	if(x != fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}

void solve() {
	scanf("%d%d%d%d", &n, &m, &p, &q);
	for(int i = 1; i < N; i++) fa[i] = i;
	//从后往前考虑，如果染过色了，就不会再染色了，所以相当于只会染色一次。
	for(int i = m; i >= 1; i--){
		int l = (i * p + q) % n + 1;
		int r = (i * q + p) % n + 1;
		if(l > r) swap(l, r);
		int x = find(l); //找到l右边第一个没有被染色的位置
		while(x <= r){
			ans[x] = i;
			fa[x] = find(x + 1);
			x = find(x);
		} 
	}
	for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
}

int main(){
	int T = 1;	
//	scanf("%d", &T);
	while(T -- ){
		solve();
	}
	
	return 0;
} 

灵活运用

《青蛙过河》

本题可以用思维+二分解决，由于这里是单链表式并查集专题，因此就用此方法做一下：模拟+二分+单链表式并查集优化。

过河思路：由于只要能过河就行，因此每次都尽量走到最远的地方。由于落脚点是有次数限制的(被一部分青蛙用过后就不能再被使用了)，因此朴素地寻找能够到达的最远的落脚点需要 $O(n)$ 的时间复杂度，这样就会超时了，我们可以用单链表式并查集优化这部分，让find(j)表示 <= j的部分中能够落脚的最右的端点。每次当某个落脚点b[j]变成0时，我们就让p[j] = find(j - 1)即可。这样就可以优化成 $O(1)$ 了。

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

//模拟：相当于把2 * x只青蛙搬运过河 

const int N = 100010;
int p[N];
int h[N], a[N], b[N];  //a[i]:i位置有多少只青蛙，b[i]:i位置能存储多少只青蛙 
int n, x;

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

bool check(int m){
	memset(a, 0, sizeof a);
	for(int i = 1; i <= n; i++) {
		if(i < n) b[i] = h[i];
		p[i] = i;
	}
	a[0] = 2 * x, a[n] = 0;
	for(int i = 0; i < n; i++){
		int j = i + m;
		if(j >= n){
			a[n] += a[i];
			a[i] = 0;
		}
		else{
			//将i位置的青蛙全部往前搬运 
			while(1){
				j = find(j);
				if(a[i] == 0 || j <= i) break;  //搬运完毕或者已经无法往前搬运 
				int c = min(a[i], b[j]);
				a[i] -= c, a[j] += c, b[j] -= c;
				if(b[j] == 0){  //这个地方之后不能再停留了,操作单链表并查集 
					p[j] = find(j - 1);
				}
			}
		}
	}
	return a[n] == 2 * x;
}

void solve() {
	scanf("%d%d", &n, &x);
	for(int i = 1; i < n; i++) scanf("%d", &h[i]);
	int l = 1, r = n;
	while(l < r){
		int mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", l);
}

int main(){
	int T = 1;	
//	scanf("%d", &T);
	while(T -- ){
		solve();
	}
	
	return 0;
}