[ABC357E] Reachability in Functional Graph 讲解

zrl123456 · 2024-06-13 21:59:32 · 题解

[ABC357E] Reachability in Functional Graph

题目考察：图论，tarjan，缩点。
题目简述：
给你一个有向图，有 n 条边和 n 个点，其中第 i（1\le i\le n）个点有一条出边，指向 a_i，求图中每个点可达点的个数之和。
其中 u（1\le u\le n）点的可达点指：

若 x 点是 u 点的可达点，且 y=a_x，则 y 点是 u 点的可达点（1\le x\le n）。

数据范围：

1\le n\le 2\times 10^5
1\le a_i\le n
我们先看一下样例 2：
很明显如果没有 \{1,2,4\} 这个环，我们直接建反图跑 topsort 即可。可以设 u 点（1\le u\le n）可达点数为 num_u，若 u=a_v，则：
num_u=num_v+1
可是这只是假设，如果有环该怎么办呢？
一个合理的想法是把这个环（强连通分量）缩成一个点，以此来跑 topsort。

那么我们就需要用到 tarjan 缩点算法，通过栈来实现。

首先我们需要的是一个时间戳 dfn_i（1\le i\le n）和一个记录他自身和他的后继节点且未访问或在栈里的的时间戳的最小值 low_i，还有一个在栈里的标记 vis_i，显然 low_i 等于：

low_i=\min(dfn_i,\min_{(i,j)\in E\land(dfn_i=0\lor vis_i=\text{true})}(dfn_j))

我们先把 i 存入栈中，然后我们对他的未访问的后继结点进行 dfs，dfs 完后若 dfn_i=low_i，则有两种情况：

他不在一个环里，这样其未访问的后继结点的 dfn_j（(i,j)\in E）一定大于 dfn_i。
它是一个环的起点，这样这个环里的所有点都能通过若干条有向边到达 i，所以这个环里的点的 low_j 都等于 dfn_i。

综上所述，他一定是一个强连通分量的起点，那么强连通分量的所有点一定都在栈的上层，那么我们把他们弹出来，并对他们进行染色。
这样我们就知道他们之中的环在哪里了，然后我们重新建图，具体请看模板题 P3387 【模板】缩点。

代码：

模板题代码：
时间复杂度为 \Theta(n)。

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=y;++i) 
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define endl '\n'
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,a[N],dfn[N],low[N],tim,sum[N],col,color[N],in[N],num[N],ans,u,v,m;
bool vis[N];
stack<int>st;
queue<int>q;
vector<int>g[N],gx[N];
inl void topsort(){
    rep(i,1,col)
        if(!in[i]){
            q.push(i);
            num[i]=sum[i];
        }
    while(!q.empty()){
        reg int u=q.front();
        q.pop();
        for(reg auto v:gx[u]){
            num[v]=max(num[v],num[u]+sum[v]);
            --in[v];
            if(!in[v]) q.push(v);
        }
    }
}
inl void tarjan(int u){
    vis[u]=1;
    st.push(u);
    dfn[u]=low[u]=++tim;
    for(reg auto v:g[u])
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]) low[u]=min(low[u],low[v]);
    if(dfn[u]==low[u]){
        reg int v;
        ++col;
        while(!st.empty()){
            v=st.top();
            st.pop();
            color[v]=col;
            vis[v]=0;
            sum[col]+=a[v];
            if(u==v) break;
        }
    }
}
signed main(){
    fst;
    memset(num,-1,sizeof(num));
    cin>>n>>m;
    rep(i,1,n) cin>>a[i];
    rep(i,1,m){
        cin>>u>>v;
        g[u].push_back(v);
    }
    rep(i,1,n)
        if(!dfn[i]) tarjan(i);
    rep(i,1,n)
        for(reg auto j:g[i])
            if(color[i]!=color[j]){
                gx[color[i]].push_back(color[j]);
                ++in[color[j]];
            }
    topsort();
    rep(i,1,col) ans=max(ans,num[i]);
    cout<<ans;
    return 0;
}

本题代码：
时间复杂度为 \Theta(n)。

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=y;++i) 
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define endl '\n'
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,a[N],dfn[N],low[N],tim,sum[N],col,color[N],in[N],num[N],ans;
bool vis[N];
stack<int>st;
queue<int>q;
vector<int>g[N];
inl void topsort(){
    rep(i,1,col)
        if(!in[i]){
            q.push(i);
            num[i]=sum[i];
        }
    while(!q.empty()){
        reg int u=q.front();
        q.pop();
        for(reg auto v:g[u]){
            num[v]=sum[v]+num[u];
            --in[v];
            if(!in[v]) q.push(v);
        }
    }
}
inl void tarjan(int u){
    vis[u]=1;
    st.push(u);
    dfn[u]=low[u]=++tim;
    if(!dfn[a[u]]){
        tarjan(a[u]);
        low[u]=min(low[u],low[a[u]]);
    }else if(vis[a[u]]) low[u]=min(low[u],low[a[u]]);
    if(dfn[u]==low[u]){
        reg int v;
        ++col;
        while(!st.empty()){
            v=st.top();
            st.pop();
            color[v]=col;
            vis[v]=0;
            ++sum[col];
            if(u==v) break;
        }
    }
}
signed main(){
    fst;
    memset(num,-1,sizeof(num));
    cin>>n;
    rep(i,1,n) cin>>a[i];
    rep(i,1,n)
        if(!dfn[i]) tarjan(i);
    rep(i,1,n)
        if(color[i]!=color[a[i]]){
            g[color[a[i]]].push_back(color[i]);
            ++in[color[i]];
        }
    topsort();
    rep(i,1,col) ans+=num[i]*sum[i];
    cout<<ans;
    return 0;
}