题解 P4645 【[COCI2006-2007 Contest#3] BICIKLI】

· · 题解

先膜楼下的chen_zhe大佬%%%

这题思路不难，可能是道假紫题。

大体思路如下：

先判断从1到2点是否有无限条路径。什么时候就会有无限条路径呢？不难想到，当出现一个环且从1节点到2节点能经过它时，就会有无数条路径可走。判断是否有环的方法很简单，只需要求强连通分量（tarjan模板不阐述)。

求好之后我们还得判断从1节点到2节点是否可以遍历到一个环，可以用一个BFS来模拟。我们先用BFS求出从1号节点出发能遍历到的所有的点。然后我们建一个反向的图，再用BFS求出在反向图中从2号点出发能遍历到的所有的点。接着判断如果某一个点既可以被2遍历到又能被1遍历到并且它在一个环之内，就说明有无限条路径，输出inf。

最后，我们在用一个BFS求出从1号点到2号点的路径总数即可。

下面有请可爱丑陋的代码酱出场qwq

#include<bits/stdc++.h>
using namespace std;
const int MAXN=101000;
struct edge{
    int to,cost;
};
stack<int> s;
int n,m,dfn[MAXN],low[MAXN],color[MAXN],vis[MAXN],used[MAXN],a[MAXN],countt[MAXN],in[MAXN];
int colornum; 
vector<int> G[MAXN];
vector<int> rG[MAXN];
inline int read()//读入优化
{
    int num=0;
    char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9')
     {
         num=num*10+ch-'0';
         ch=getchar();
     }
    return num; 
}
int cnt;
void tarjan(int u)//Tarjan模板，求出强连通分量
{
    cnt++;
    dfn[u]=low[u]=cnt;
    used[u]=true;
    s.push(u);
    vis[u]=true;
    for(int i=0; i<G[u].size(); i++)
    {
        int v=G[u][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
        {
            if(vis[v])
            {
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
    if(dfn[u]==low[u])
    {
        colornum++;
        while(s.top()!=u)
        {
            int t=s.top();
            s.pop();
            color[t]=colornum;
            vis[t]=false;
        }
        s.pop();
        color[u]=colornum;
        vis[u]=false;
    }
}
void bfs1(int x)//求出从1号节点出发能遍历到的所有的点
{
    memset(used,0,sizeof(used));
    queue<int>q;
    q.push(x);
    used[x]=true;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(int i=0; i<G[v].size(); i++)
        {
            if(!used[G[v][i]])
            {
                used[G[v][i]]=true;//判断是否能被1遍历到
                q.push(G[v][i]);
            }
            in[G[v][i]]++;
        }
    }
}
void bfs2(int x)//求出在逆向图中从2号节点出发能遍历到的所有的点
{
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(x);
    vis[x]=true;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(int i=0; i<rG[v].size(); i++)
        {
            if(!vis[rG[v][i]])
            {
                vis[rG[v][i]]=true;//判断是否能被2遍历到
                q.push(rG[v][i]);
            }
        }
    }
}
void bfs3(int x)
{
    queue<int>q;
    q.push(x);
    countt[x]=1;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(int i=0; i<G[v].size(); i++)
        {
            if(vis[G[v][i]])
            {
                countt[G[v][i]]+=countt[v];
                countt[G[v][i]]%=1000000000;//取模
                if(!--in[G[v][i]]) q.push(G[v][i]);//小优化
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        x=read(),y=read();
        G[x].push_back(y);//邻接表存储
        rG[y].push_back(x);//建反向图
    }
    for(int i=1; i<=n; i++)
    if(!dfn[i]) tarjan(i);
    bfs1(1);
    bfs2(2);
    for(int i=1; i<=n; i++)
    a[color[i]]++;//统计每个强连通分中节点个数
    for(int i=1; i<=n; i++)
    if(used[i]&&vis[i]&&a[color[i]]!=1)//可以被2遍历到又能被1遍历到并且在一个环之内
    {
        cout<<"inf";
        return 0;
    }
    bfs3(1);
    cout<<countt[2];
    return 0;
}

管理大大求过