题目链接:https://atcoder.jp/contests/abc295/tasks/abc295_g
题目意思:给你一颗以1为根的有向树,询问有两种情况:
第一种询问是在u,v中加一条边,保证v是可以到u的。
第二种询问是问u所能到的最小的节点的序号是多少。
大致思路:
每加一条边,会在新图形成一个新的强连通分量。
可以用并查集来维护新加入的边,答案就是当前点所在点集的祖先(此处非常巧妙)。
代码(c++):
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int f[N];
int p[N];
int find(int x){
if (x!=p[x]) p[x] = find(p[x]);
return p[x];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for (int i=1;i<=n;i++) p[i] = i;
for (int i=2;i<=n;i++) cin>>f[i];
int q;
cin>>q;
for (int i=1;i<=q;i++){
int t;
cin>>t;
if (t==1){
int x,y;
cin>>x>>y;
x = find(x);
while(x>y){
int Y = find(f[x]);
int X = find(x);
p[X] = Y;
x = find(x);
}
}else{
int x;
cin>>x;
cout<<find(x)<<'\n';
}
}
}