题目
这个地方有 (n) 个城镇，从 (1sim n) 编号，
其中有 (m) 条单向道路连接它们。
比赛将在 (1) 号城镇开始并在 (2) 号城镇结束。
主办方想知道，一共有多少条不同的路线？
分析
首先此题数据范围得开到(10^5)不要问我为什么。
然后主要是判无限比较恶心，考虑正反跑一次，
两次都经过的点才能被算进去，然后拓扑排序一下
再套个dp就可以了
代码
#include <cstdio>
#include <cctype>
#include <vector>
#define rr register
using namespace std;
const int N=100011; vector<int>K[N];
struct node{int y,next;}e[N];
int q[N],v[N],as[N],head,tail,deg[N],dp[N],n,m;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
signed main(){
n=iut(),m=iut();
for (rr int i=1;i<=m;++i){
rr int x=iut(),y=iut();
e[i]=(node){y,as[x]},++deg[y],
K[y].push_back(x),as[x]=i;
}
q[head=tail=1]=2,v[2]=1;
while (head<=tail){
rr int x=q[head++],len=K[x].size();
for (rr int j=0;j<len;++j) if (!v[K[x][j]])
v[K[x][j]]=1,q[++tail]=K[x][j];
}
if (!v[1]) return !printf("0");
for (rr int i=1;i<=n;++i)
if (v[i]){
rr int len=K[i].size();
for (rr int j=0;j<len;++j)
if (!v[K[i][j]]) --deg[i];
}else deg[i]=0;
for (rr int i=1;i<=n;++i) v[i]=0;
q[head=tail=1]=v[1]=1;
while (head<=tail){
rr int x=q[head++];
for (rr int i=as[x];i;i=e[i].next)
if (!v[e[i].y]) v[e[i].y]=1,q[++tail]=e[i].y;
}
for (rr int i=1;i<=n;++i)
if (!v[i]){
deg[i]=0;
for (rr int j=as[i];j;j=e[j].next)
--deg[e[j].y];
}
q[head=tail=1]=1;
while (head<=tail){
rr int x=q[head++];
for (rr int i=as[x];i;i=e[i].next)
if (--deg[e[i].y]==0) q[++tail]=e[i].y;
}
for (rr int i=1;i<=n;++i)
if (deg[i]>0&&v[i]) return !printf("inf");
dp[1]=1;
for (rr int i=1;i<=tail;++i)
for (rr int j=as[q[i]];j;j=e[j].next)
dp[e[j].y]=(dp[e[j].y]+dp[q[i]])%1000000000;
return !printf("%d",dp[2]);
}