题解：P12760 [POI 2018 R2] 自行车道 Bike paths

Lysra · 2025-06-19 10:47:00 · 题解

Description

给你一个图，满足：

若不存在从 v 到 u 的路径，则从 u 到 v 至多只有一条路径。

问每个点可以到达多少个点。

Solution

首先一个强连通分量中的点一定能够互相到达，先缩点。

然后考虑这个性质意味着什么：缩点后，若不存在从 v 到 u 的路径，但从 u 到 v 存在多条路径，则这个图存在“环”。

这里的“环”是不考虑方向的，即将整张图视为无向图的情况下的环。

这也就意味着将整张图视为无向图的情况下，缩点后我们会得到一颗树。

但值得注意，这棵树不一定是内向树或者外向树，它的方向是不定的，所以不能直接找一个根进行 dfs。

但可以考虑记忆化记录每个点能够到达的点的个数，跑多次 dfs，那么这题就做完了。

时间复杂度 O(n+m)。

Code

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
using namespace std;
struct star{
    int next,to;
}e[N];
vector<int>vt[N];
bool vis[N];
map<pair<int,int>,bool>mp;
int n,m,dfn[N],low[N],sck[N],fnt,tot,c[N];
int cnt,head[N],qwq,bel[N],in[N],siz[N];
void add(int u,int v){
    e[++cnt].next=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}
void Tarjan(int x){
    dfn[x]=low[x]=++tot;
    sck[++fnt]=x,vis[x]=true;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to;
        if(!dfn[y]){
            Tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        qwq++;
        while(int z=sck[fnt--]){
            vis[z]=false;
            bel[z]=qwq,siz[qwq]++;
            if(x==z) break;
        }
    }
}
void rebuild(){
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=e[j].next){
            int y=e[j].to;
            if(bel[i]==bel[y]||mp[{bel[i],bel[y]}]) continue;
            vt[bel[i]].push_back(bel[y]);
            mp[{bel[i],bel[y]}]=1;
        }
    }
}
int dfs(int x){
    if(c[x]) return c[x];
    c[x]=siz[x];
    for(int v:vt[x]){
        dfs(v);
        c[x]+=c[v];
    }
    return c[x];
}
signed main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        add(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) Tarjan(i);
    rebuild();
    for(int i=1;i<=qwq;i++) dfs(i);
    for(int i=1;i<=n;i++) cout<<c[bel[i]]-1<<endl;
    return 0;
}