P9760

Spouter_27 · 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;
}