【图论/基环树】AcWing 392. 会合

本文主要是介绍【图论/基环树】AcWing 392. 会合，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

分析

这题就是一道需要分类讨论的图论。。

注意到题目中每个点只有一条出边，也就是说给出的图是一个内向的基环树森林。

首先进行预处理：

• 开一个并查集，这能够将两个点不在同一棵基环树的情况筛掉。
• 利用内向树随便找一个点跳到基环树的环（环上所有点记为“根”）。然后建反图，在反图上跑一遍 \(\texttt{dfs}\) 以标记 \(vis\)，以达到所有点都会在 \(\texttt{dfs}\) 过程中访问且仅访问一次。
• \(\texttt{dfs}\) 过程中处理 LCA（倍增实现）的祖先数组 p[][]。
• 处理基环树的环的大小，方便求环上 \(x\to y\) 的距离 cycdis。

下面开始处理查询：

• 最简单的情况当然是退化成树上的 LCA 问题，直接检查是否跳到同一个点即可。
• 如果发现两个点就算跳到了基环树的根也不同，那么就求一次 \(x\) 跳到 \(y\) 的总距离以及 \(y\) 到 \(x\) 的总距离，按照题意所要求的关系进行讨论即可。

事实上，这题的难点在于如何处理需要的信息，主体的查询并不复杂。

更多细节见代码。

彩蛋

《8000ms 与 TLE》

// Problem: 会合
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/394/
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << (x) << endl
#define endl '\n'
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()

#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;

inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=5e5+50;

int n, Q;
int w[N];
vector<int> g[N];

int f[N];

int find(int x){
	return x==f[x]? x: f[x]=find(f[x]);
}

bool vis[N], isrt[N];
int p[N][20], dep[N];

void dfs(int u, int fa, int d, int fir, int sec){
	vis[u]=true;
	dep[u]=d;
	if(!isrt[u]){
		p[u][0]=fa;
		rep(i,1,19) p[u][i]=p[p[u][i-1]][i-1];
	}
	else p[u][0]=u;
	for(auto go: g[u]){
		if(u==sec && go==fir) continue;
		dfs(go, u, (isrt[go]? 0: d+1), fir, sec);
	}
}

pii lca(int u, int v){
	bool swp=false;
	if(dep[u]<dep[v]) swap(u, v), swp=true;
	dwn(i,19,0) if(dep[u]-(1<<i)>=dep[v]) u=p[u][i];
	if(u==v) return {u, v};
	
	dwn(i,19,0){
		int pu=p[u][i], pv=p[v][i];
		if(pu!=pv && !isrt[pu]){
			u=pu, v=pv;
		}
	}
	return swp==false? (pii){p[u][0], p[v][0]}: (pii){p[v][0], p[u][0]};
}

int cycn[N];
int cid[N], ctot, sz[N];

int cycdis(int sz, int u, int v){
	int x=cycn[u], y=cycn[v];
	if(y>x) return y-x;
	return sz-(x-y);
}

int main(){
	cin>>n>>Q;
	rep(i,1,n) f[i]=i;
	rep(i,1,n){
		read(w[i]);
		g[w[i]].pb(i);
		f[find(i)]=find(w[i]);
	}
	
	rep(i,1,n) if(!vis[i]){
		int u=i;
		while(!vis[u]) vis[u]=true, u=w[u];
		int rt=u;
		int ts=0;
		++ctot;
		do{
			isrt[rt]=true;
			cycn[rt]=++ts;
			cid[rt]=ctot;
			sz[ctot]++;
			rt=w[rt];
		}while(rt!=u);
		dfs(u, 0, 0, u, w[u]);
	}
	
	while(Q--){
		int u, v; read(u), read(v);
		if(find(u)!=find(v)){
			puts("-1 -1");
			continue;
		}
		
		auto [x, y]=lca(u, v);
		if(x==y){
			cout<<dep[u]-dep[x]<<' '<<dep[v]-dep[x]<<endl;
			continue;
		}

		int dx=dep[u]-dep[x], dy=dep[v]-dep[y];
		int fir=cycdis(sz[cid[x]], x, y);
		int sec=cycdis(sz[cid[x]], y, x);
		if(max(dx+fir, dy)!=max(dx, dy+sec)){
			if(max(dx+fir, dy)<max(dx, dy+sec)) cout<<dx+fir<<' '<<dy<<endl;
			else cout<<dx<<' '<<dy+sec<<endl;
		}
		else if(min(dx+fir, dy)!=min(dx, dy+sec)){
			if(min(dx+fir, dy)<min(dx, dy+sec)) cout<<dx+fir<<' '<<dy<<endl;
			else cout<<dx<<' '<<dy+sec<<endl;
		}
		else cout<<dx+fir<<' '<<dy<<endl;
	}
	return 0;
}

这篇关于【图论/基环树】AcWing 392. 会合的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！