P4645 [COCI2006-2007#3] BICIKLI
题意：求一张 \(n\) 个点的有向图中 \(1\) 号点到 \(2\) 号点的路径数。
首先考虑不在 \(1\) 号点到 \(2\) 号点的路径上的那些点不会对答案产生影响，于是先预处理出所有 \(1\) 号点到 \(2\) 号点路径上经过的点。先在原图上以 \(1\) 号点为起点对所有能到达的点进行染色，再在反图上以 \(2\) 号点为起点对所有能到达的点进行染色。两次都被染上色的点就在 \(1\) 号点到 \(2\) 号点的路径上。
然后考虑什么时候会有无数条满足条件的路径。发现当且仅当路径上有环时，可以经过任意次环以产生无数条路径。
剩下的情况就是 \(\text{DAG}\) 了，直接跑拓扑用 \(\text{dp}\) 进行路径计数。
复杂度 \(O(n + m)\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll SIZE = 200005;
const ll mod = 1e9;
ll n, m;
ll head[SIZE], ver[SIZE*2], nxt[SIZE*2], tot;
vector<ll> e[SIZE];
bool c1[SIZE], c[SIZE];
ll d[SIZE];
ll ans[SIZE];
inline ll rd(){
ll f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return f*x;
}
void add(ll x, ll y){
ver[++tot] = y, nxt[tot] = head[x];
head[x] = tot;
}
void dfs1(ll x){
c1[x] = 1;
for(int i = head[x]; i; i = nxt[i]){
ll y = ver[i];
if(c1[y]) continue;
dfs1(y);
}
}
void dfs2(ll x){
c[x] = 1;
for(int i = 0; i < e[x].size(); i++){
ll y = e[x][i];
if(c[y]) continue;
dfs2(y);
}
}
struct E{
ll x, y;
}ee[SIZE];
int main(){
n = rd(), m = rd();
assert(n <= 100000 && m <= 100000);
for(int i = 1; i <= m; i++){
ll x = rd(), y = rd(); ee[i].x = x, ee[i].y = y;
add(x, y); e[y].push_back(x);
}
dfs1(1);
dfs2(2);
ll cnt = 0;
for(int i = 1; i <= n; i++) c[i] &= c1[i], cnt += c[i];
for(int i = 1; i <= m; i++){
if(!c[ee[i].x] || !c[ee[i].y]) continue;
d[ee[i].y]++;
}
if(d[1] != 0){
printf("inf");
return 0;
}
queue<int> q;
q.push(1); ll z = 0;
ans[1] = 1;
while(q.size()){
ll x = q.front(); q.pop();
z++;
for(int i = head[x]; i; i = nxt[i]){
ll y = ver[i];
d[y]--; ans[y] = (ans[y] + ans[x]) % mod;
if(d[y] == 0){
q.push(y);
}
}
}
if(z < cnt) printf("inf");
else printf("%lld", ans[2]);
return 0;
}