[拓扑排序][tarjan缩点]自行车比赛

本文主要是介绍[拓扑排序][tarjan缩点]自行车比赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

自行车赛在一个很大的地方举行，有N个镇，用1到N编号，镇与镇之间有M条单行道相连，起点设在镇1，终点设在镇2。
问从起点到终点一共有多少种不同的路线。两条路线只要不使用完全相同的道路就被认为是不同的。

Input

第一行两个整数：N和M(1<=N<=10000,1<=M<=100000)，表示镇的数量和道路的数量。
接下来M行，每行包含两个不同的整数A和B，表示有一条从镇A到镇B的单行道。
两个镇之间有可能不止一条路连接。

Output

输出不同路线的数量，如果答案超过9位，只需输出最后9位数字。如果有无穷多的路线，输出“inf”。

Sample Input

输入1：
6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4

输入2：
6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3

输入3：
31 60
1 3
1 3
3 4
3 4
4 5
4 5
5 6
5 6
6 7
6 7
…
…
…
28 29
28 29
29 30
29 30
30 31
30 31
31 2
31 2

分析

首先偷偷告诉你：
这题并没有inf的数据。。。虽然会存在强联通分量，但是并没有在1~2的必经之路上的
这种统计的，明显就是用拓扑序列来继承方案数下去
所以我们要打拓扑排序
然后因为拓扑的前提是一个有向无环图，而（有可能）存在强连通分量，所以我们打个tarjan缩点
嗯，没了
还有如果遇到小于九位的是不用补零的

#include <iostream>
#include <cstdio>
#include <queue>
#define rep(i,a,b) for (i=a;i<=b;i++)
#define pot(i,l,p) for (i=l;i;i=p[i])
using namespace std;
int n,m,cnt;
int d[10001];int list[10001],u[100001],v[100001],next[100001];
int lst[10001],u1[100001],v1[100001],nxt[100001];int low[10001],dfn[10001],target;
int stk[10001],top;
bool instk[10001];queue<int> q;
int ind[10001];bool b[10001];
int f[10001];bool judge;
void tarjan(int i)
{int j;dfn[i]=low[i]=++target;stk[++top]=i;instk[i]=1;pot(j,list[i],next){if (!dfn[v[j]]){tarjan(v[j]);low[i]=min(low[v[j]],low[i]);}elseif (instk[v[j]])low[i]=min(low[i],dfn[v[j]]);}if (low[i]==dfn[i]){cnt++;int o;do{o=stk[top];top--;d[o]=cnt;instk[o]=0;}while (i!=o);}
}
void topsort()
{int i;rep(i,1,cnt)if (!ind[i]) q.push(i);while (!q.empty()){int k=q.front();q.pop();pot(i,lst[k],nxt){if (!(--ind[v1[i]])) q.push(v1[i]);if (f[v1[i]]+f[k]>=1000000000) judge=1;f[v1[i]]=(f[v1[i]]+f[k])%1000000000;}}
}
void init()
{int i;scanf("%d%d",&n,&m);rep(i,1,m){scanf("%d%d",&u[i],&v[i]);next[i]=list[u[i]];list[u[i]]=i;}
}
void doit()
{int i,j;rep(i,1,n)if (!dfn[i]) tarjan(i);rep(i,1,m)if (d[u[i]]!=d[v[i]]){u1[i]=d[u[i]];v1[i]=d[v[i]];ind[v1[i]]++;nxt[i]=lst[u1[i]];lst[u1[i]]=i;}f[d[1]]=1;topsort();
}
void print()
{if (judge){printf("%d",(int)(f[d[2]]/100000000)%10);printf("%d",(int)(f[d[2]]/10000000)%10);printf("%d",(int)(f[d[2]]/1000000)%10);printf("%d",(int)(f[d[2]]/100000)%10);printf("%d",(int)(f[d[2]]/10000)%10);printf("%d",(int)(f[d[2]]/1000)%10);printf("%d",(int)(f[d[2]]/100)%10);printf("%d",(int)(f[d[2]]/10)%10);printf("%d",f[d[2]]%10);}elseprintf("%d",f[d[2]]);
}
int main()
{init();doit();print();
}