自动搬运

查看原文

来自洛谷，原作者为

	Spouter_27 **

搬运于2025-08-24 22:51:36，当前版本为作者最后更新于2023-10-18 11:45:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先对原图建出圆方树。

如果 $a_u=u$，那么 $u$ 的答案是 $0$。

如果从 $v$ 走到 $u$ 能抓住 Luka，当且仅当 $u$ 在圆方树 $a_v$ 到 $a_u$ 的链上，这样从 $a_v$ 走到 $a_u$ 必须经过 $u$。

枚举 $u$，再枚举与 $u$ 相邻的点 $v$，如果满足上述条件，就把 $v$ 标记为制胜点，$v$ 的答案最多就是 $1$。判断是否在链上可以用树剖。

最后在原图跑一边 bfs 就可以求出每个点的答案。当然如果没有一个点是制胜点就全是 $-1$。复杂度是 $O(m\log n)$ 的。

不怎么好看的代码：

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define deb(x) cerr<<"Line: "<<__LINE__<<", val= "<<x<<"; \n"
typedef long long ll;
#define pii pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
const ll N=4e5+10,M=1e6+10;
inline ll read(){
	ll a=0,x=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	x=-x;
		c=getchar();
	}
	while(isdigit(c)){
		a=a*10+c-'0';
		c=getchar();
	}
	return a*x;
}
ll n,m;
ll idx=0,dfn[N],low[N],cnt,s[N],top,ans[N],a[N];
ll de[N],sz[N],bs[N],tp[N],fa[N];
vector<ll> bss[N];
struct Graph{
	ll nt[M],hd[N],tt,to[M];
	Graph(){
		memset(nt,0,sizeof(nt));
		memset(hd,0,sizeof(hd));
		memset(to,0,sizeof(to));
		tt=1;
	}
	void push(ll u,ll v){
		to[++tt]=v;
		nt[tt]=hd[u];
		hd[u]=tt;
	} 	
	void tarjan(ll nw,ll en){
		ll son=0;
		low[nw]=dfn[nw]=++idx;
		s[++top]=nw;
		for(int i=hd[nw];i;i=nt[i]){
			ll v=to[i];
			if(!dfn[v]){
				son++;tarjan(v,nw);
				low[nw]=min(low[nw],low[v]);
				if(low[v]>=dfn[nw]){
					cnt++;
					while(s[top+1]!=v){
						bss[cnt].push_back(s[top--]);
					}
					bss[cnt].push_back(nw);
				}
			}else if(v!=en)	low[nw]=min(low[nw],dfn[v]);
		}
		if(en==0&&son==0){
			bss[++cnt].push_back(nw);
		}
	}
	void dfs(ll nw,ll en){
		sz[nw]=1;
		fa[nw]=en;
		de[nw]=de[en]+1;
		for(int i=hd[nw];i;i=nt[i]){
			if(to[i]==en)	continue;
			dfs(to[i],nw);
			sz[nw]+=sz[to[i]];
			if(!bs[nw]||sz[bs[nw]]<sz[to[i]])	bs[nw]=to[i];
		}
	}
	void dfs2(ll nw,ll zp){
		tp[nw]=zp;
		dfn[nw]=++idx;
		if(bs[nw])	dfs2(bs[nw],zp);
		for(int i=hd[nw];i;i=nt[i]){
			if(to[i]==fa[nw]||to[i]==bs[nw])	continue;
			dfs2(to[i],to[i]);
		}
	}
}G1,G2;
bool chk(ll x,ll y,ll v){
	while(tp[x]!=tp[y]){
		if(de[tp[x]]<de[tp[y]])	swap(x,y);
		if(dfn[tp[x]]<=dfn[v]&&dfn[v]<=dfn[x])	return true;
		x=fa[tp[x]];
	}
	if(de[x]<de[y])	swap(x,y);
	if(dfn[y]<=dfn[v]&&dfn[v]<=dfn[x])	return true;
	return false;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=m;i++){
		ll u=read(),v=read();
		G1.push(u,v),G1.push(v,u);
	}
	for(int i=1;i<=n;i++){
		ans[i]=1e18;
		if(a[i]==i)	ans[i]=0;
		if(dfn[i])	continue;
		top=0;
		G1.tarjan(i,0);
	}
	for(int i=1;i<=cnt;i++){
		for(unsigned j=0;j<bss[i].size();j++){
			G2.push(n+i,bss[i][j]);
			G2.push(bss[i][j],n+i);
		}
	}
	idx=0;
	G2.dfs(1,0);
	G2.dfs2(1,1);
	for(int nw=1;nw<=n;nw++){
		for(int i=G1.hd[nw];i;i=G1.nt[i]){
			ll v=G1.to[i];
			if(ans[v]<=1)	continue;
			if(chk(a[nw],a[v],nw))	ans[v]=1;
		}
	}
	queue<ll> q;
	for(int i=1;i<=n;i++){
		if(ans[i]==0)	q.push(i);
	}
	for(int i=1;i<=n;i++){
		if(ans[i]==1)	q.push(i);
	}
	while(!q.empty()){
		ll nw=q.front();
		q.pop();
		for(int i=G1.hd[nw];i;i=G1.nt[i]){
			ll v=G1.to[i];
			if(ans[nw]+1<ans[v]){
				q.push(v);
				ans[v]=ans[nw]+1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(ans[i]==1e18)	printf("-1 ");
		else printf("%lld ",ans[i]);
	}
	return 0;
}