C01【模板】并查集——信息学奥赛算法_哔哩哔哩_bilibili
并查集¶
并查集（Union-Find）数据结构是一种用于处理一些不交集的合并及查询问题的数据结构。它支持两种操作：合并（Union）和查询（Find）。以下是并查集的基本实现原理：
基本概念¶
-
集合：并查集是由一系列不相交的集合组成的集合。
-
代表元素（根节点）：每个集合中都会有一个元素作为该集合的代表元素。在实现中，通常用代表元素来标识一个集合。
初始化¶
在并查集的初始化阶段，每个元素都被看作是一个单独的集合，其代表元素就是它自己。
parent[i] = i; // 初始时，每个节点的父节点是它自己
查找（Find）¶
查找操作用于确定一个元素属于哪个集合，这通常是通过找到该元素的代表元素来实现的。
int find(int x) {
if (parent[x] == x) {
return x; // 如果x是其自己的父节点，那么x是代表元素
}
return find(parent[x]); // 递归查找x的父节点的代表元素
}
为了提高效率，通常会在查找过程中进行**路径压缩**，即将路径上的所有节点直接连接到代表元素上。
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
合并（Union）¶
合并操作用于将两个集合合并成一个集合。通常的实现方式是选择两个集合的代表元素，然后将一个集合的代表元素作为另一个集合的代表元素的子节点。
void unionSets(int x, int y) {
int rootX = find(x); // 查找x的代表元素
int rootY = find(y); // 查找y的代表元素
if (rootX != rootY) {
parent[rootY] = rootX; // 将rootY的代表元素设置为rootX
}
}
为了防止合并后树变得不平衡，通常会使用**按秩合并**（按大小合并）的策略，即总是将秩较小的树合并到秩较大的树中。
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX] += 1; // 如果秩相同，选择一个作为根，并增加其秩
}
}
}
总结¶
并查集通过将每个集合的代表元素作为树的根节点，并通过父节点指针来表示树结构，从而实现了高效的合并和查询操作。路径压缩和按秩合并是两种常用的优化方法，它们可以显著提高并查集的操作效率。在最优情况下，并查集的操作几乎可以在常数时间内完成。
例题 #1 亲戚¶
规定：\(x\) 和 \(y\) 是亲戚，\(y\) 和 \(z\) 是亲戚，那么 \(x\) 和 \(z\) 也是亲戚。如果 \(x\)，\(y\) 是亲戚，那么 \(x\) 的亲戚都是 \(y\) 的亲戚，\(y\) 的亲戚也都是 \(x\) 的亲戚。
输入格式
第一行：三个整数 \(n,m,p\)，（\(n,m,p \le 5000\)），分别表示有 \(n\) 个人，\(m\) 个亲戚关系，询问 \(p\) 对亲戚关系。
以下 \(m\) 行：每行两个数 \(M_i\)，\(M_j\)，\(1 \le M_i,~M_j\le n\)，表示 \(M_i\) 和 \(M_j\) 具有亲戚关系。
接下来 \(p\) 行：每行两个数 \(P_i,P_j\)，询问 \(P_i\) 和 \(P_j\) 是否具有亲戚关系。
输出格式
\(p\) 行，每行一个 Yes 或 No。表示第 \(i\) 个询问的答案为“具有”或“不具有”亲戚关系。
核心代码
路径压缩
int find(x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
合并
void merge(int a,int b){
a=find(a),b=find(b);
fa[a]=b;
}
按秩合并
void merge(int a,int b){
a=find(a),b=find(b);
if(x==y)return ;
if(sz[a]>sz[b])swap(a,b);
fa[a]=b;
sz[b]+=sz[a];//sz[]初始化为1
}
带权并查集¶
并查集维护并查集信息
维护并查集大小
不要忘记怎么写！只需要merge时修改即可。
int find(int a){
if(fa[a]==a)return a;
return fa[a]=find(fa[a]);
}
void merge(int faa,int fbb){
if(faa!=fbb)fa[faa]=fbb,sz[fbb]+=sz[faa];
}
//merge(find(e[cur].a),find(e[cur].b));
例题 #1 [NOI2002] 银河英雄传说¶
杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成 \(30000\) 列，每列依次编号为 \(1, 2,\ldots ,30000\)。之后，他把自己的战舰也依次编号为 \(1, 2, \ldots , 30000\)，让第 \(i\) 号战舰处于第 \(i\) 列，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为 M i j，含义为第 \(i\) 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 \(j\) 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。
然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。
在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第 \(i\) 号战舰与第 \(j\) 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。
作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。
维护并查集大小，并且以此更新该点到链头的距离
int find(int x){
if(fa[x]==x)return x;
int f=fa[x];
fa[x]=find(fa[x]);
dis[x]+=dis[f];
sz[x]+=sz[fa[x]];
return fa[x];
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
fa[fx]=fy;
dis[fx]+=sz[fy];
sz[fx]+=sz[fy];//更新集合大小
sz[fy]=sz[fx];//记录当前点实在集合的大小
}
并查集求最小环¶
例题 #1 [NOIP2015 提高组] 信息传递¶
https://www.luogu.com.cn/problem/P2661
有 \(n\) 个同学（编号为 \(1\) 到 \(n\)）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 \(i\) 的同学的信息传递对象是编号为 \(T_i\) 的同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？
输入格式
输入共 \(2\) 行。
第一行包含 \(1\) 个正整数 \(n\)，表示 \(n\) 个人。
第二行包含 \(n\) 个用空格隔开的正整数 \(T_1,T_2,\cdots,T_n\)，其中第 \(i\) 个整数 \(T_i\) 表示编号为 \(i\) 的同学的信息传递对象是编号为 \(T_i\) 的同学，\(T_i\leq n\) 且 \(T_i\neq i\)。
输出格式
共一行一个整数，表示游戏一共可以进行多少轮。
- 对于 \(100\%\) 的数据，\(n\le 2\times 10^5\)。
/*
CB Ntsc
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rd read()
inline int read() {
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
inline void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
//
const int N = 1e6 + 5;
const int INF = 1e9 + 5;
const int MOD = 998244353;
bool f1;
int t[N], fa[N], d[N], ans, n;
bool f2;
int find(int x){
if(fa[x]!=x){
int l=fa[x];
fa[x]=find(fa[x]);
d[x]+=d[l];
}return fa[x];
}
signed main() {
n=rd;
for(int i=1;i<=n;i++){
fa[i]=i;t[i]=rd;
}
ans=INF;
for(int i=1;i<=n;i++){
int a=find(i),b=find(t[i]);
if(a!=b){
fa[a]=b;d[i]=d[t[i]]+1;
}else{
ans=min(ans,d[i]+d[t[i]]+1);
}
}
cout<<ans;
return 0;
}
扩展域并查集¶
例题 #1 [NOI2001] 食物链¶
动物王国中有三类动物 \(A,B,C\)，这三类动物的食物链构成了有趣的环形。\(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)。
现有 \(N\) 个动物，以 \(1 \sim N\) 编号。每个动物都是 \(A,B,C\) 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 \(N\) 个动物所构成的食物链关系进行描述：
-
第一种说法是
1 X Y，表示 \(X\) 和 \(Y\) 是同类。 -
第二种说法是
2 X Y，表示 \(X\) 吃 \(Y\)。
此人对 \(N\) 个动物，用上述两种说法，一句接一句地说出 \(K\) 句话，这 \(K\) 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
-
当前的话与前面的某些真的话冲突，就是假话；
-
当前的话中 \(X\) 或 \(Y\) 比 \(N\) 大，就是假话；
-
当前的话表示 \(X\) 吃 \(X\)，就是假话。
你的任务是根据给定的 \(N\) 和 \(K\) 句话，输出假话的总数。
对于全部数据，\(1\le N\le 5 \times 10^4\)，\(1\le K \le 10^5\)。
知识
并查集，扩展域并查集
代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int fa[N*3],n,k,ans;
int find(int x){
return (fa[x]!=x)?fa[x]=find(fa[x]):x;
}
void uni(int a,int b){
fa[find(a)]=find(b);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n*3;i++)fa[i]=i;
while(k--){
int a,b,op;
scanf("%d%d%d",&op,&a,&b);
if(a>n||b>n){
ans++;continue;
}
if(op==1){
if(find(a+n)==find(b)||find(a)==find(n+b))ans++;
else uni(a,b),uni(a+n,b+n),uni(a+n+n,b+n+n);
}else {
if(find(a)==find(b)||find(a)==find(b+n))ans++;
else uni(a+n,b),uni(a+n+n,b+n),uni(a,b+n+n);
}
}
printf("%d\n",ans);
}
//////////////GOOD LUCK ,NTSC/////////////
例题 #2 [CEOI1999] Parity Game¶
Alice 和 Bob 在玩一个游戏：他写一个由 \(0\) 和 \(1\) 组成的序列。Alice 选其中的一段（比如第 \(3\) 位到第 \(5\) 位），问他这段里面有奇数个 \(1\) 还是偶数个 \(1\)。Bob 回答你的问题，然后 Alice 继续问。Alice 要检查 Bob 的答案，指出在 Bob 的第几个回答一定有问题。有问题的意思就是存在一个 \(01\) 序列满足这个回答前的所有回答，而且不存在序列满足这个回答前的所有回答及这个回答。
第 \(1\) 行一个整数 \(n\)，是这个 \(01\) 序列的长度。
第 \(2\) 行一个整数 \(m\)，是问题和答案的个数。
第 \(3\) 行开始是问题和答案，每行先有两个整数，表示你询问的段的开始位置和结束位置。然后是 Bob 的回答。odd表示有奇数个 \(1\)，even 表示有偶数个 \(1\)。
输出一行，一个数 \(x\)，表示存在一个 \(01\) 序列满足第 \(1\) 到第 \(x\) 个回答，但是不存在序列满足第 \(1\) 到第 \(x+1\) 个回答。如果所有回答都没问题，你就输出所有回答的个数。
对于 \(100\%\) 的数据，\(1 \le n \leq 10^9\)，\(m \leq 5 \times 10^3\)。
这里我们考虑前缀和性质。要明确控制欲并查集可以维护什么，才能想到做法。
转化为并查集，即若[l,r]和为奇数，那么\(q_r\)和\(q_{l-1}\)（\(q_i\)表示[1,i]前缀和）的奇偶性相同，反之不相同。于是我们维护前缀和的奇偶性关系即可。
开两倍空间为[1,n][n+1,2n]，合并a,b表示\(q_a,q_{b-1}\)奇偶性相同，合并a,b+n表示不同。
#include <bits/stdc++.h>
#include <queue>
#include <iostream>
#define rep(l, r, i) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(r, l, i) for (int i = r, END##i = l; i >= END##i; --i)
using namespace std;
// #define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
#define X(j) i[j]
#define Y(j) (dp[j] + (i[j] + L) * (i[j] + L))
#define rd read()
int read() {
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
const int N =2e5 + 5;
const int INF = 1e18;
const int MOD = 998244353;
int m,n,a[N],b[N],v[N];
int fa[N<<1];
int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
void merge(int a,int b){
int faa=find(a),fbb=find(b);
if(faa!=fbb) fa[faa]=fbb;
}
int e[N];
int cnt;
signed main(){
n=rd,m=rd;
for(int i=1;i<=m;i++){
a[i]=rd-1,b[i]=rd;
// cerr<<a[i]<<' '<<b[i]<<endl;
e[++cnt]=a[i];
e[++cnt]=b[i];
string s;
cin>>s;
if(s=="odd")v[i]=1;
// cerr<<v[i]<<endl;
}
sort(e+1,e+cnt+1);
int l=unique(e+1,e+cnt+1)-e-1;
// for(int i=1;i<=l*2;i++)cerr<<e[i]<<' ';
// cerr<<endl;
for(int i=1;i<=l*2;i++)fa[i]=i;//两倍初始化！
for(int i=1;i<=m;i++){
// cerr<<i<<' '<<a[i]<<' '<<b[i]<<' '<<endl;
a[i]=lower_bound(e+1,e+l+1,a[i])-e;
b[i]=lower_bound(e+1,e+l+1,b[i])-e;
// cerr<<i<<' '<<a[i]<<' '<<b[i]<<' '<<endl;
if(v[i]){
if(find(a[i])==find(b[i])){
cout<<i-1<<endl;
return 0;
}else{
merge(a[i],b[i]+l);
merge(a[i]+l,b[i]);
}
}else{
if(find(a[i])==find(b[i]+l)){
cout<<i-1<<endl;
return 0;
}else{
merge(a[i],b[i]);
merge(a[i]+l,b[i]+l);
}
}
}
cout<<m<<endl;
}
扩展域并查集判定二分图¶
并查集判断二分图(tourist做法) - yHan234 - 博客园
注意这里的二分图没有规定那些点必须在哪边，因此当且仅当图中出现奇环时二分图不成立，或者说是**不能构成**二分图。
用扩展域可以判定二分图。我们开两倍空间的并查集，左边为\(L(1\sim n)\)，右边为\(R(n+1\sim 2n)\)。我们把每个点分裂为两个点为u\(_1,u_2\)，编号为u,n+u。在我们连接u,v时，就连接\(u_1-v_2\)和\(u_2-v_1\)。最后如果某一时刻存在\(p,p_n\)在同一个集合内，二分图就不成立了。
这里的意思就是\(u_1\)默认u在左部，\(u_2\)默认u在右部。连接\(u_1,-v_2\)就表示假设u在左部且v在右部，另一种情况亦然。如果存在某个p满足\(p_1\)和\(p_2\)间接或直接相连，那么就说明无论假设p在左部还是右部，为了尽可能让与p相连的点满足二分图性质，则会最终得到一个点x相连的p应该在假设的p的另外一部。即p无论放在哪一部都会得到相反的结论。二分图无法成立。
例题 #1 [NOIP2010 提高组] 关押罪犯¶
S 城现有两座监狱，一共关押着 \(N\) 名罪犯，编号分别为 \(1\sim N\)。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 \(c\) 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 \(c\) 的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了 \(N\) 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入格式
每行中两个数之间用一个空格隔开。第一行为两个正整数 \(N,M\)，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 \(M\) 行每行为三个正整数 \(a_j,b_j,c_j\)，表示 \(a_j\) 号和 \(b_j\) 号罪犯之间存在仇恨，其怨气值为 \(c_j\)。数据保证 \(1<a_j\leq b_j\leq N, 0 < c_j\leq 10^9\)，且每对罪犯组合只出现一次。
输出格式
共一行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。
对于 \(30\%\) 的数据有 \(N\leq 15\)。
对于 \(70\%\) 的数据有 \(N\leq 2000,M\leq 50000\)。
对于 \(100\%\) 的数据有 \(N\leq 20000,M\leq 100000\)。
/*
CB Ntsc
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
const int N=1e6+5;
const int INF=1e9+5;
const int MOD=1e9+7;
bool f1;
int fa[N];
int q,n,m,ans,cnt,enm[N],T;
bool f2;
#define rd read()
inline int read()
{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
struct node{
int a,b,c;
}t[N];
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
void uni(int x,int y){
int fx=find(x),fy=find(y);
fa[fx]=fy;
}
bool check(int x,int y){
int fx=find(x),fy=find(y);
return fx==fy;
}
bool cmp(node a,node b){
return a.c>b.c;
}
signed main(){
// freopen("chfran.in","r",stdin);
// freopen("chfran.out","w",stdout);
n=rd;m=rd;
for(int i=1;i<=m;i++){
t[i].a=rd;t[i].b=rd;t[i].c=rd;
}
for(int i=1;i<=n;i++)fa[i]=i;
sort(t+1,t+m+1,cmp);
for(int i=1;i<=m;i++){
if(check(t[i].a,t[i].b)){
cout<<t[i].c<<endl;
return 0;
}
if(!enm[t[i].a]){
enm[t[i].a]=t[i].b;
}else{
uni(enm[t[i].a],t[i].b);
}
if(!enm[t[i].b]){
enm[t[i].b]=t[i].a;
}else{
uni(enm[t[i].b],t[i].a);
}
}
cout<<0<<endl;
return 0;
}
可持久化并查集¶
给定 \(n\) 个集合，第 \(i\) 个集合内初始状态下只有一个数，为 \(i\)。
有 \(m\) 次操作。操作分为 \(3\) 种：
-
1 a b合并 \(a,b\) 所在集合； -
2 k回到第 \(k\) 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态； -
3 a b询问 \(a,b\) 是否属于同一集合，如果是则输出 \(1\)，否则输出 \(0\)。
对于 \(100\%\) 的数据，\(1\le n\le 10^5\)，\(1\le m\le 2\times 10^5\)，\(1 \le a, b \le n\)。
代码分析¶
struct node{
int lc,rc,v,rnk;
}tr[M];
秩
int getrnk(int x,int l,int r,int p){//单点查询秩
if(l==r)return tr[x].rnk;
int mid=l+r>>1;
if(p<=mid)return getrnk(tr[x].lc,l,mid,p);
return getrnk(tr[x].rc,mid+1,r,p);
}
void changernk(int pre,int &now,int l,int r,int p,int v){//修改秩（树的高度）
now=++idx;
tr[now]=tr[pre];
if(l==r){
tr[now].rnk=max(tr[now].rnk,v);//要比对取最大值
return;
}
int mid=l+r>>1;
if(p<=mid)changernk(tr[pre].lc,tr[now].lc,l,mid,p,v);
else changernk(tr[pre].rc,tr[now].rc,mid+1,r,p,v);
return ;
}
查询
int query(int x,int l,int r,int p){//查询父节点
if(l==r){
return tr[x].v;
}
int mid=l+r>>1;
if(p<=mid)return query(tr[x].lc,l,mid,p);
return query(tr[x].rc,mid+1,r,p);
}
int find(int x,int p){
int fa=query(x,1,n,p);
if(p==fa)return fa;
return find(x,fa);//x是版本
}
修改&合并
void change(int pre,int now,int l,int r,int p,int fa){//修改父节点
now=++idx;
tr[now]=tr[pre];
if(l==r){
tr[now].v=fa;
return;
}
int mid=l+r>>1;
if(p<=mid)change(tr[pre].lc,tr[now].lc,l,mid,p,fa);
else change(tr[pre].rc,tr[now].rc,mid+1,r,p,fa);
}
void merge(int a,int b,int i){
a=find(rt[i-1],a),b=find(rt[i-1],b);
// cerr<<"OK\n";
if(a==b){rt[i]=rt[i-1];return ;}
if(getrnk(rt[i-1],1,n,a)>getrnk(rt[i-1],1,n,b))swap(a,b);
// int t;
change(rt[i-1],rt[i],1,n,a,b);
int t=rt[i];
changernk(t,rt[i],1,n,b,getrnk(rt[i-1],1,n,a)+1);//sz[b]+=sz[a];
}
完整代码¶
WA64pts
/*
CB Ntsc
*/
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define mp make_pair
const int N = 2e5 + 5;
const int M = 1e7 + 5;
const int INF = 1e9 + 5;
const int MOD = 1e9 + 7;
bool f1;
int rt[N];
int q, n, m, ans, idx, T;
vector<int> b;
bool f2;
#define rd read()
inline int read() {
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
inline void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
struct node{
int lc,rc,v,rnk;
}tr[N*50];//50倍空间 ,32不够
void build(int &x,int l,int r){
x=++idx;
if(l==r){
tr[x].v=l;
tr[x].rnk=1;
return;
}
build(tr[x].lc,l,l+r>>1);
build(tr[x].rc,(l+r>>1)+1,r);
}
int getrnk(int x,int l,int r,int p){//单点查询秩
if(l==r)return tr[x].rnk;
int mid=l+r>>1;
if(p<=mid)return getrnk(tr[x].lc,l,mid,p);
return getrnk(tr[x].rc,mid+1,r,p);
}
void changernk(int pre,int &now,int l,int r,int p,int v){//修改秩（树的高度）
now=++idx;
tr[now]=tr[pre];
if(l==r){
tr[now].rnk=max(tr[now].rnk,v);//要比对取最大值
return;
}
int mid=l+r>>1;
if(p<=mid)changernk(tr[pre].lc,tr[now].lc,l,mid,p,v);
else changernk(tr[pre].rc,tr[now].rc,mid+1,r,p,v);
return ;
}
// void insert(int pre,int &now,int l,int r,int v){
// now=++idx;//动态开点.新插入一个点 为了可以方便的用这个now更新上一个函数空间的tr[now].lc(或rc),我们就引用一下
// tr[now]=tr[pre];//复制旧点的信息
// tr[now].v++;//点权+1,因为插入的树在now的区间内
// if(l==r)return;
// int mid=l+r>>1;
// if(v<=mid)insert(tr[pre].lc,tr[now].lc,l,mid,v);
// else insert(tr[pre].rc,tr[now].rc,mid+1,r,v);
// }
int query(int x,int l,int r,int p){//查询父节点
if(l==r){
return tr[x].v;
}
int mid=l+r>>1;
if(p<=mid)return query(tr[x].lc,l,mid,p);
return query(tr[x].rc,mid+1,r,p);
}
int find(int x,int p){
int fa=query(x,1,n,p);
if(p==fa)return fa;
return find(x,fa);//x是版本
}
int change(int pre,int l,int r,int p,int fa){//修改父节点
//这里不能引用&now直接修改，在merge中会出错->note
int now=++idx;
tr[now]=tr[pre];
if(l==r){
tr[now].v=fa;
return now;
}
int mid=l+r>>1;
if(p<=mid)tr[now].lc=change(tr[pre].lc,l,mid,p,fa);
else tr[now].rc=change(tr[pre].rc,mid+1,r,p,fa);
return now;
}
void merge(int a,int b,int i){
a=find(rt[i-1],a),b=find(rt[i-1],b);
// cerr<<"OK\n";
if(a==b){rt[i]=rt[i-1];return ;}
if(getrnk(rt[i-1],1,n,a)>getrnk(rt[i-1],1,n,b))swap(a,b);
// int t;
// change(rt[i-1],rt[i],1,n,a,b);
int t=change(rt[i-1],1,n,a,b);
// int t=rt[i];
changernk(t,rt[i],1,n,b,getrnk(rt[i-1],1,n,a)+1);//sz[b]+=sz[a];
}
signed main() {
// freopen("chfran.in", "r", stdin);
// freopen("chfran.out", "w", stdout);
n=rd;m=rd;
build(rt[0],1,n);
for(int i=1;i<=m;i++) {
int op=rd;
if(op==1){
int a=rd,b=rd;
merge(a,b,i);
}if(op==2){
int k=rd;
rt[i]=rt[k];
}if(op==3){
int a=rd,b=rd;
rt[i]=rt[i-1];
if(find(rt[i],a)==find(rt[i],b))cout<<1<<endl;
else cout<<0<<endl;
}
}
}
/*
1
2 5 1
0 0 1
0 0 4
*/
Hint¶
int change(int pre,int l,int r,int p,int fa){//修改父节点
//这里不能引用&now直接修改，在merge中会出错->note
...
}
原因：
不要乱修改原来的点值！
AC
/*
CB Ntsc
*/
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define mp make_pair
const int N = 2e5 + 5;
const int M = 1e7 + 5;
const int INF = 1e9 + 5;
const int MOD = 1e9 + 7;
bool f1;
int rt[N];
int q, n, m, ans, idx, T;
vector<int> b;
bool f2;
#define rd read()
inline int read() {
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
inline void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
struct node{
int lc,rc,v,rnk;
}tr[N*50];//32倍空间
void build(int &x,int l,int r){
x=++idx;
if(l==r){
tr[x].v=l;
tr[x].rnk=1;
return;
}
build(tr[x].lc,l,l+r>>1);
build(tr[x].rc,(l+r>>1)+1,r);
}
int getrnk(int x,int l,int r,int p){//单点查询秩
if(l==r)return tr[x].rnk;
int mid=l+r>>1;
if(p<=mid)return getrnk(tr[x].lc,l,mid,p);
return getrnk(tr[x].rc,mid+1,r,p);
}
void changernk(int pre,int &now,int l,int r,int p,int v){//修改秩（树的高度）
now=++idx;
tr[now]=tr[pre];
if(l==r){
tr[now].rnk=max(tr[now].rnk,v);//要比对取最大值
return;
}
int mid=l+r>>1;
if(p<=mid)changernk(tr[pre].lc,tr[now].lc,l,mid,p,v);
else changernk(tr[pre].rc,tr[now].rc,mid+1,r,p,v);
return ;
}
// void insert(int pre,int &now,int l,int r,int v){
// now=++idx;//动态开点.新插入一个点 为了可以方便的用这个now更新上一个函数空间的tr[now].lc(或rc),我们就引用一下
// tr[now]=tr[pre];//复制旧点的信息
// tr[now].v++;//点权+1,因为插入的树在now的区间内
// if(l==r)return;
// int mid=l+r>>1;
// if(v<=mid)insert(tr[pre].lc,tr[now].lc,l,mid,v);
// else insert(tr[pre].rc,tr[now].rc,mid+1,r,v);
// }
int query(int x,int l,int r,int p){//查询父节点
if(l==r){
return tr[x].v;
}
int mid=l+r>>1;
if(p<=mid)return query(tr[x].lc,l,mid,p);
return query(tr[x].rc,mid+1,r,p);
}
int find(int x,int p){
int fa=query(x,1,n,p);
if(p==fa)return fa;
return find(x,fa);//x是版本
}
int change(int pre,int l,int r,int p,int fa){//修改父节点
int now=++idx;
tr[now]=tr[pre];
if(l==r){
tr[now].v=fa;
return now;
}
int mid=l+r>>1;
if(p<=mid)tr[now].lc=change(tr[pre].lc,l,mid,p,fa);
else tr[now].rc=change(tr[pre].rc,mid+1,r,p,fa);
return now;
}
//int modify(int now, int l, int r, int pos, int fa) { //修改父节点（合并）
// int p = ++idx;
// tr[p] = tr[now];
// if (l == r) {
// tr[p].v = fa;
// return p;
// }
// int mid = (l + r) / 2;
// if (pos <= mid) {
// tr[p].lc = modify(tr[now].lc, l, mid, pos, fa);
// } else {
// tr[p].rc = modify(tr[now].rc, mid + 1, r, pos, fa);
// }
// return p;
//}
void merge(int a,int b,int i){
a=find(rt[i-1],a),b=find(rt[i-1],b);
// cerr<<"OK\n";
if(a==b){rt[i]=rt[i-1];return ;}
if(getrnk(rt[i-1],1,n,a)>getrnk(rt[i-1],1,n,b))swap(a,b);
// int t;
// change(rt[i-1],rt[i],1,n,a,b);
int t=change(rt[i-1],1,n,a,b);
// int t=rt[i];
changernk(t,rt[i],1,n,b,getrnk(rt[i-1],1,n,a)+1);//sz[b]+=sz[a];
}
signed main() {
// freopen("chfran.in", "r", stdin);
// freopen("chfran.out", "w", stdout);
n=rd;m=rd;
build(rt[0],1,n);
for(int i=1;i<=m;i++) {
int op=rd;
if(op==1){
int a=rd,b=rd;
merge(a,b,i);
}if(op==2){
int k=rd;
rt[i]=rt[k];
}if(op==3){
int a=rd,b=rd;
rt[i]=rt[i-1];
if(find(rt[i],a)==find(rt[i],b))cout<<1<<endl;
else cout<<0<<endl;
}
}
}
/*
1
2 5 1
0 0 1
0 0 4
*/