P4645 [COCI2006-2007#3] BICIKLI 题解

· · 题解

题解区基本全是正着搜一遍再反着搜一遍，来一篇缩点的题解。

无限走的情况很容易让人想到强联通分量，假设走到一个大小大于等于 2 强联通分量里且还能到达终点，那么就会出现无限路径。但假设一个大小为 2 的强连通分量中包含终点，则不会产生影响。

缩点后跑一遍拓补排序即可，下面上代码。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define rst(a,x) memset(a,x,sizeof(a))
#define ls p<<1
#define rs p<<1|1
#define FAST ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using namespace std;

const int N(1e5+5);
const int P(1e9);

int n,m,dfn[N],low[N],tot,cnt,scc[N],sta[N],tp,sz[N],dp[N],st,ed,in[N],wrong[N]; 
vector <int> G[N],g[N];

void tarjan(int u){
    dfn[u]=low[u]=++tot;sta[++tp]=u;
    for(auto v:G[u]){
        if(!dfn[v]){
            tarjan(v);
            cmin(low[u],low[v]);
        }else if(!scc[v]){
            cmin(low[u],low[v]);
        }
    }
    if(dfn[u]==low[u]){
        int v;cnt++;
        do{
            v=sta[tp--];
            scc[v]=cnt;
            sz[cnt]++;
            if(v==2) ed=cnt;
            if(v==1) st=cnt;
        }while(u!=v);
    }
}

struct edge{
    int u,v;
}e[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        e[i]={u,v};
    }
    tarjan(1);
    for(int i=1;i<=m;i++){
        if(scc[e[i].u]!=scc[e[i].v]&&scc[e[i].u]&&scc[e[i].v]){
            g[scc[e[i].u]].push_back(scc[e[i].v]);
            in[scc[e[i].v]]++;
        }
    }
    queue <int> q;
    for(int i=1;i<=cnt;i++){
        if(!in[i]){
            q.push(i);
        }   
        if(sz[i]>1) wrong[i]=1;
        if(ed==i&&sz[i]==2) wrong[i]=0;
    }
    dp[st]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(auto v:g[u]){
            wrong[v]|=wrong[u];
            dp[v]+=dp[u];dp[v]%=P;
            in[v]--;
            if(!in[v]) q.push(v);
        }
    }
    if(wrong[ed]) cout<<"inf";
    else cout<<dp[ed];
    return 0;
}