返回信息流今遇到一笔试题，题目如下：
给你一个有向图，N点M边，问从1号点出发到N号点截止有多少条路径？
这道题坑挺多的，我发现的有这些：
（1）有可能有环，此时答案是无穷多，但只要走到N号点就不能再走，因此诸如
1-5-2-3-4-5-2-3-4.....(N=5)的循环不算。
（2）有可能1点和N点不连通，此时答案是0
（3）有可能有多重边、自环。
我的思路是，先判环（tarjan算法？或者，染色？），如果没环，令dp[i]表示从1到i的路径条数，则dp[i]=sum(dp[j]),j为i的前驱节点，可是dfs搜的时候在遇到分叉的时候，顺序总是出问题，请问如何解决？
刚才又想到一个坑，就是这个环有可能出现在1～n的路径外面，这种在跑tarjan或者染色的时候怎么处理？
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91900同步于 2017/1/1
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】请教一笔试题，如何判断图中两点间的路径条数？
lhy963
2017/1/1镜像同步12 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
去年803是什么我没做过，如果只是判断有没有路径用并查集不就得了？
哦，是有向图啊，那就从1点搜呗，搜得到n就有，搜不到n就没有？直觉而已
【 在 YHNO1 的大作中提到: 】
: 去年803的只是判断有没有路径吧？比这个题简单多了
我觉得是不是可以这么做：
1：做一遍DFS，算1可以到的点构成的图G'，在DFS时如果无法到达N则解为0
2：在G'中以1为起点做一遍拓扑排序，计算到N的拓扑序列，在做拓扑排序时无法到N则解为无穷（说明有环）
3：根据拓扑序列做DP，计算路径条数
特别判断一下这些东西
你提到的N在环内可以做这样的处理：把N点的出边去掉
你提到的环在外面可以这样处理：
1:1点无法到达这个环，在DFS步骤已经解决
2:在外面的环不到N，但是这种情况下产生的拓扑序列会包含N点，所以做拓扑序列时我们有两个退出条件：1，已经搜索到N，2：不存在入度为零的点
其实我写的已经差不多接近对的了，但是问题应该还是出在了判环的问题上
因为有一个测试点答案是一个数，我输出了infinite
```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define RE(x) freopen(x,"r",stdin)
#define WR(x) freopen(x,"w",stdout)
#define INF 0x3f3f3f3f
const int M = 1e9;
const double PI = acos(-1.0);
int n,m;
vector<int> g[10005];
vector<int> g2[10005];
deque<int> tp;
ll dp[10005];
int vis[10005];
bool cy=false;
void dfs(int u) {
vis[u]=1;
for(int i=0;i<g[u].size();i++) {
int v=g[u][i];
if(vis[v]==1 && vis[n]!=2) //这里改了下模板，碰出来一个vis[n]!=2
cy=true;
else if(vis[v]==0)
dfs(v);
}
vis[u]=2;
}
void dfs2(int u) {
vis[u]=1;
for(int i=0;i<g[u].size();i++) {
int v=g[u][i];
if(!vis[v])
dfs2(v);
}
tp.push_front(u);
}
int main() {
//RE("in.txt");WR("out.txt");
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
cin>>n>>m;
for(int i=m;i>0;i--) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
g2[v].push_back(u);
}
dfs(1);
if(cy) {
cout<<"INFINITE PATHS"<<endl;
}
else {
dp[1]=1;
memset(vis,0,sizeof(vis));
dfs2(1);
for(int i=0;i<tp.size();i++) {
int u=tp[i];
for(int j=0;j<g2[u].size();j++) {
int v=g2[u][j];
dp[u]=(dp[u]+dp[v])%M;
}
}
cout<<dp[n]<<endl;
}
}
```
【 在 hlcjj 的大作中提到: 】
: 我觉得是不是可以这么做：
: 1：做一遍DFS，算1可以到的点构成的图G'，在DFS时如果无法到达N则解为0
: 2：在G'中以1为起点做一遍拓扑排序，计算到N的拓扑序列，在做拓扑排序时无法到N则解为无穷（说明有环）
: ...................
你没有解决你之前说的环在外面的情况，
比如
1 2
2 3
3 2
1 4
如果你想用判环的方法的话，可以先从n点逆向dfs一遍看看哪些点是无法到n的，然后再判环
【 在 lhy963 的大作中提到: 】
: 其实我写的已经差不多接近对的了，但是问题应该还是出在了判环的问题上
: 因为有一个测试点答案是一个数，我输出了infinite
: [md]
: ...................
oeis中给出了这题的数列，并引了一篇相关的论文，看了一下references，这道题貌似只有这个叫Hiroaki Iwashita的日本人研究过。。。。
p.s.此论文的作者算到了26*26，论文里说N=22时用时28w秒。
【 在 nuanyangyang 的大作中提到: 】
: 话说这个题真的这么简单吗？ http://www.bilibili.com/video/av362069/
那个是无向图而且不能走重复路径所以难
【 在 nuanyangyang 的大作中提到: 】
: 话说这个题真的这么简单吗？ http://www.bilibili.com/video/av362069/