P4645 [COCI2006-2007#3] BICIKLI(Tarjan+topsort求到某点的方案数）

P4645 [COCI2006-2007#3] BICIKLI - 洛谷 | 计算机科学教育新生态

思路：

我们考虑输出inf的情况，可以发现当从1出发到2经过的任意一个点处于一个环内时，路径条数是无穷多的。

有向图上从s到t的经过点，就是从s出发所能经过的所有点与从t出发在反图上所能经过的所有点的交集。

进行拓扑排序时的点的入度，是从s出发所能经过的所有点与从t出发在反图上所能经过的所有点的交集的这张图上的入读，那些不能既被s经过又被t经过的点到这张图上的边所提供的入度是无用的。

Code:

constexpr int N=1e5+5,mod=1e9;

#define fi first
#define se second

int n,m;
int low[N],dfn[N],stk[N],instk[N],tot,top;
int scc[N],sz[N],cnt;
vector<int> e[N],e1[N];
PII p[N];
bool vis1[N],vis2[N];
int d[N],ans[N];

void Tarjan(int u)
{
    dfn[u]=low[u]=++tot;
    stk[++top]=u,instk[u]=1;
    for(auto t:e[u])
    {
        if(!dfn[t])
        {
            Tarjan(t);
            low[u]=min(low[u],low[t]);
        }
        else if(instk[t]) low[u]=min(low[u],dfn[t]);
    }

    if(dfn[u]==low[u])
    {
        int y;
        ++cnt;
        do{
            y=stk[top--];instk[y]=0;
            scc[y]=cnt;
            sz[cnt]++;
        }while(y!=u);
    }
}

void dfs1(int u)
{
    if(vis1[u]) return ;
    vis1[u]=true;
    for(auto t:e[u])
    {
        dfs1(t);
        d[t]++;
    }
}

void dfs2(int u)
{
    if(vis2[u]) return ;
    vis2[u]=true;
    for(auto t:e1[u])
    {
        dfs2(t);
    }
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>p[i].fi>>p[i].se;
        e[p[i].fi].push_back(p[i].se);
        e1[p[i].se].push_back(p[i].fi);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) Tarjan(i);
    dfs1(1),dfs2(2);

    for(int i=1;i<=n;i++)
    {
        if(vis1[i]&&vis2[i]&&sz[scc[i]]!=1)
        {
            cout<<"inf";
            return ;
        }
    }

    queue<int> q;
    q.push(1);
    ans[1]=1;
    while(q.size())
    {
        int t=q.front();q.pop();
        for(int v:e[t])
        {
            if(vis2[v])
            {
                ans[v]=(ans[v]+ans[t])%mod;
                d[v]--;
                if(!d[v]) q.push(v);
            }
        }
    }
    cout<<ans[2];
}

原文地址：https://blog.csdn.net/2302_79372568/article/details/144294752

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！