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 secondint 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];
}