CONTENT: 并查集 II
DETAIL: 并查集的按秩合并、可持久化并查集
BB
被师兄催更了 QAQQQQQ
本次算法实验5，让蒟蒻get了额外的并查集的两个点！Amazing！
Introduction
本次的主要内容涉及到了并查集的按秩合并、可持续化并查集
黑白树 - HYSBZ 3319
Description
给定一棵树，边的颜色为黑或白，初始时全部为白色。维护两个操作：
1.查询u到根路径上的第一条黑色边的标号。
2.将u到v 路径上的所有边的颜色设为黑色。
Notice:这棵树的根节点为1
Sample Input
5 4
1 2
1 3
2 4
2 5
1 2
2 2 3
1 3
1 4
Sample Output
0
2
1
Solution —— 并查集
补题系列QAQ（6个月前，用树剖一直TLE，直到才知道怎么用并查集写）
边染黑查离根最近的黑边，相当于白边连通的点集被黑边割断，点集割断是比较难考虑的，不妨倒过来考虑，在一个有黑边的图中将边染白
首先正向染黑并记录最开始染黑的时间，全部操作完成后，将始终为白的边的两端并入dsu，维护深度最小的为dsu的根，这个时候该根的父边就是该dsu中每个点离根最近的黑边
接下来把操作倒过来做，每次如果是染黑操作就看看哪些边是这个时间染黑的，将其染白，并入dsu（维护深度最小的为dsu的根），如果是询问就输出该点在dsu中的根的连接父亲的边
看哪些边是这个时间的染黑的，只需要在最开始正向染黑完成后，把所有黑边拷贝出来，按照时间排个序就能快速查询
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 15;
struct edge {
int v, nxt;
};
struct info {
int op, u, v;
};
struct edgeColorInfo {
int v, idx;
bool operator < (const edgeColorInfo& b) const {
return idx < b.idx;
}
};
edge e[N << 1];
int head[N], tot;
int ft[N], dpt[N], preEdge[N], par[N];
info input[N];
int isColor[N];
int ans[N], ansTot, ecTot;
edgeColorInfo ec[N];
inline char get(void) {
static char buf[1000000], *p1 = buf, *p2 = buf;
if (p1 == p2) {
p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
inline int read() {
int x = 0;
static char c;
bool minus = false;
for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') minus = true;
for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get());
if (minus) x = -x;
return x;
}
char WritellBuffer[1024];
template <typename T>
inline void write(T a,char end) {
ll cnt=0,fu=1;
if(a<0) {
putchar('-');
fu=-1;
}
do {
WritellBuffer[++cnt]=fu*(a%10)+'0';
a/=10;
} while(a);
while(cnt) {
putchar(WritellBuffer[cnt]);
--cnt;
}
if(end) putchar(end);
}
inline void dsuInit() {
for(int i = 0; i < N; i++) {
ft[i] = i;
}
}
inline void init() {
memset(head, -1, sizeof(head));
tot = ansTot = dpt[1] = par[1] = 0;
preEdge[1] = -1;
}
inline void addEdge(int u, int v) {
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
inline int find(int x) {
return ft[x] == x ? x : ft[x] = find(ft[x]);
}
inline void merge(int x, int y) {
int p = find(x), q = find(y);
if(p != q) {
if(dpt[p] > dpt[q]) {
swap(p, q);
}
ft[q] = p;
}
}
void dfs(int u) {
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(v == par[u]) {
continue;
}
dpt[v] = dpt[u] + 1;
par[v] = u;
preEdge[v] = i >> 1;
dfs(v);
}
}
void color(int u, int v, int idx) {
u = find(u), v = find(v);
while(u != v) {
if(dpt[u] > dpt[v]) {
swap(u, v);
}
isColor[v] = idx;
merge(v, par[v]);
v = find(v);
}
}
int main() {
int n = read(), m = read();
init();
dsuInit();
memset(isColor, 0, sizeof(isColor));
for(int i = 1; i <= n - 1; i++) {
int u = read(), v = read();
addEdge(u, v);
addEdge(v, u);
}
dfs(1);
for(int i = 1; i <= m; i++) {
input[i].op = read(), input[i].u = read();
if(input[i].op == 2) {
input[i].v = read();
color(input[i].u, input[i].v, i);
}
}
dsuInit();
ecTot = 0;
for(int i = 2; i <= n; i++) {
if(isColor[i] == 0) {
merge(i, par[i]);
} else {
ec[++ecTot] = edgeColorInfo{i, isColor[i]};
}
}
sort(ec + 1, ec + 1 + ecTot);
for(int i = m; i >= 1; i--) {
if(input[i].op == 1) {
ans[ansTot++] = preEdge[find(input[i].u)] + 1;
} else {
while(ecTot > 0 && ec[ecTot].idx == i) {
merge(par[ec[ecTot].v], ec[ecTot].v);
ecTot--;
}
}
}
for(int i = ansTot - 1; i >= 0; i--) {
write(ans[i], '\n');
}
}
Extends
目前看来，貌似从儿子找根比从根找儿子更容易
Bond - UVA 11354
Description
给定一个无向带权图，多组询问，问(u,v)上的最大边权，同时要求最大边权最小
Sample Input
2
3
1 2
1 3
9
9 4
4 3
1 3
7 4
1 6
5 7
2 4
6 8
Sample Output
Case #1: 3
Case #2: 21
Solution —— MST + 并查集的按秩合并
本题之前写过solution于是跳过一部分
如果u所在的dsu与v所在的dsu使用按秩合并合并，那么这一条连边在dsu中必然在(u,v)的路径上，但是并不知道具体是哪一条，如果能够在这一条边上维护所需的最大、最小等一整条路径上的突出信息（？），就可以通过暴力爬树到lca的方法，遍历一整条路径获取该值
在本题中，使用kruska求mst，因为kruskal求mst的性质，(u,v)路径上的最大值所在边一定是将(u,v)连通的边，那么在dsu中暴力爬到lca(u,v)，取一整条路径的最大值，即使不知道这条边是哪一条，也可以获取到最大值这一信息
#include <bits/stdc++.h>
#define lson l, m
#define rson m + 1, r
using namespace std;
const int N = (int)1e5 + 5;
typedef long long ll;
struct edge {
int u, v, w;
bool operator < (const edge& b) {
return w < b.w;
}
};
edge e[N];
int ft[N], sz[N], val[N];
inline void init(int n) {
for(int i = 0; i <= n; i++) {
ft[i] = i;
sz[i] = 1;
val[i] = 0;
}
}
inline int find(int x) {
return ft[x] == x ? x : find(ft[x]);
}
inline void merge(int x, int y, int w) {
int p = find(x), q = find(y);
if(p != q) {
if(sz[p] < sz[q]) {
swap(p, q);
}
ft[q] = p;
sz[p] += sz[q];
val[q] = w;
}
}
inline void kruskal(int m) {
sort(e, e + m);
for(int i = 0; i < m; i++) {
int u = e[i].u, v = e[i].v;
merge(u, v, e[i].w);
}
}
inline int solve(int u, int v) {
int ans = 0;
while(u != v) {
if(sz[u] < sz[v]) {
swap(u, v);
}
ans = max(ans, val[v]);
v = ft[v];
}
return ans;
}
int main(){
int n, m;
bool isFirst = true;
while(~scanf("%d%d", &n, &m)) {
if(!isFirst) {
puts("");
}
isFirst = false;
init(n);
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
}
kruskal(m);
int q;
scanf("%d", &q);
while(q--) {
int u, v;
scanf("%d%d", &u, &v);
printf("%d\n", solve(u, v));
}
}
}
Extends
路径压缩虽然效率高，但是会破坏并查集的树形结构，而按秩合并不会
可持久化并查集 by zky - HYSBZ 3673
Description
n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
0<n,m<=2*10^4
Sample Input
5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2
Sample Output
1
0
1
Solution —— 可持久化并查集
可持久化并查集一般用主席树实现，毕竟就是可持久化数组嘛，每次合并改一个根的值，正好满足主席树的要求
一般采用按秩合并的方式，听说可以用路径压缩（不会，告辞 QAQ
#include <bits/stdc++.h>
#define lson l, m
#define rson m + 1, r
using namespace std;
const int N = (int)2e4 + 5;
typedef long long ll;
int root[N * 200], ls[N * 200], rs[N * 200], val[N * 200], sz[N * 200];
int tot;
int a[N];
inline void init() {
tot = 1;
}
inline void build(int& rtx, int l, int r) {
rtx = tot++;
if(l == r) {
sz[rtx] = 1;
val[rtx] = a[l];
return;
}
int m = (l + r) >> 1;
build(ls[rtx], lson);
build(rs[rtx], rson);
}
inline int query(int rtx, int pos, int l, int r) {
if(l == r) {
return rtx;
}
int m = (l + r) >> 1;
if(pos <= m) {
return query(ls[rtx], pos, lson);
} else {
return query(rs[rtx], pos, rson);
}
}
inline void update(int& rtx, int rty, int pos, int x, int l, int r) {
rtx = tot++;
if(l == r) {
val[rtx] = x;
return;
}
ls[rtx] = ls[rty];
rs[rtx] = rs[rty];
int m = (l + r) >> 1;
if(pos <= m) {
update(ls[rtx], ls[rty], pos, x, lson);
} else {
update(rs[rtx], rs[rty], pos, x, rson);
}
}
inline int find(int x, int rtx, int n) {
int nodey = query(rtx, x, 1, n);
return val[nodey] == x ? nodey : find(val[nodey], rtx, n);
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)) {
init();
for(int i = 1; i <= n; i++) {
a[i] = i;
}
build(root[0], 1, n);
for(int i = 1; i <= m; i++) {
int op, a, b;
scanf("%d%d", &op, &a);
if(op != 2) {
scanf("%d", &b);
}
if(op == 2) {
root[i] = root[a];
continue;
}
root[i] = root[i - 1];
if(op == 1) {
int nodeP = find(a, root[i], n);
int nodeQ = find(b, root[i], n);
if(val[nodeP] == val[nodeQ]) {
continue;
}
if(sz[nodeP] < sz[nodeQ]) {
swap(nodeP, nodeQ);
}
sz[nodeP] += sz[nodeQ];
update(root[i], root[i - 1], val[nodeQ], val[nodeP], 1, n);
} else {
int nodeP = find(a, root[i], n);
int nodeQ = find(b, root[i], n);
//printf("||%d %d\n", val[nodeP], val[nodeQ]);
printf("%d\n", val[nodeP] == val[nodeQ] ? 1 : 0);
}
}
}
}
