计算两个节点之间的路径数

Question

王国连通性

对查尔斯国王来说，这是繁荣的一年，他正在迅速扩大他的王国。一个美丽的新王国最近已经建成，在这个王国里有许多城市由多条单向道路连接。两个城市可能由多条道路直接连接，这是为了确保高度连接。

在这个新王国中，查尔斯国王将其中一个城市作为他的金融首都，另一个作为战争首都，他希望这两个首都之间有高度的连通性。一对城市的连通性，比如城市A和城市B，被定义为从城市A到城市B的不同路径的数量。如果可能的话，一条路径可以多次使用一条道路。如果两条路径不使用完全相同的道路序列，则被认为是不同的。

新王国有N个城市，编号为1到N，M条单行道。城市1是货币之都，城市N是战争之都。

作为新王国最好的程序员之一，你需要回答金融资本和战争资本的连通性，即从城市1到城市N的不同路径的数量。

输入说明：

第一行包含两个整数N和M。

然后沿着M行走，每行有两个整数，比如x和y，1

输出说明：

打印从城市1到城市N的不同路径数，模为100000000（10^9）。如果有无限多条不同的路径，请打印“无限路径”（引号是为了清楚起见）。

样品输入：

5 5 1 2 2 4 2 3 3 4 4 5

样本输出：

2个

样品输入：

5 5 1 2 4 2 2 3 3 4 4 5

样本输出：

无限路径

约束条件：

2个

1.

两个城市可以通过两条以上的道路连接，在这种情况下，这些道路将被视为不同的道路，以计算不同的路径

我用来解决这个问题的算法是：

>

检测节点n是否可从节点1到达。

it not则所需的ans为0

如果它是可达的，那么通过从节点0执行dfs来查找图中是否有任何循环

如果有循环，则打印无限路径

如果没有循环，使用递归计算所需的an

• F（n）=1

我已将解决方案实施为：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<pair<int, int> > > g;

int seen[10001] = {0};

int colour[10001] = {0};
bool has_cycle(int u) {
    colour[u] = 1;
    for(int i = 0; i < g[u].size(); i++) {
            if(colour[g[u][i].first]==1) return true;
            if(!colour[g[u][i].first])
            if(has_cycle(g[u][i].first)) return true;
    }
    colour[u] = 2;
    return false;
}


bool reachable(int u, int v) {
     if(u==v) return true;
     seen[u] = true;
     for(int i = 0; i < g[u].size(); i++) {
             if(!seen[g[u][i].first]) {
                                      if(reachable(g[u][i].first, v)) return true;
             }
     }
     return false;
}

long long mm[10001] = {0};
long long solve(int u, int n) {
     if(u==n) return mm[u]=1;
     if(mm[u]!=-2) return mm[u];
     long long ans = 0;
     for(int i = 0; i < g[u].size(); i++) {
             ans += ((g[u][i].second%1000000000)*(solve(g[u][i].first, n)%1000000000)%1000000000);
             ans %= 1000000000;
     }
     return mm[u]=ans;
}

long edge[100001];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    g.resize(n);
    for(int i = 0; i < m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            x--; y--;
            edge[i] = x*100000+y;
    }

    sort(edge, edge+m);
    edge[m] = -1;
    int last = edge[0];
    int cnt = 1;
    for(int i = 1; i <= m; i++) {
            if(edge[i]!=last || i==m) {
                              int u, v;
                              u = last/100000;
                              v = last%100000;
                              if(i!=0) {       
                                       g[u].push_back(make_pair(v, cnt));
                              }
                              cnt = 1;
            } else {
                   cnt++;
            }
            last = edge[i];
    }


    for(int i = 0; i < n; i++) mm[i] = -2;
    if(reachable(0, n-1)) {
      if(has_cycle(0)) printf("INFINITE PATHS\n");
      else 
      printf("%lld\n", solve(0, n-1)%1000000000);
    } else printf("0\n");
}

我无法检测此算法的问题

Answer 1

你可以参考我的代码

#include <iostream>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include "string.h"
#define MODE 1000000000
using namespace std;

int main () {
    vector<int> adj[10001], inv_adj[10001];
    int indegree[10001];
    int visited[10001];
    int ranks[10001];
    long long total[10001];
    int N, M;
    cin >> N >> M;

    memset(indegree, 0, (N+1)*sizeof(int));
    adj[0].push_back(1); 
    inv_adj[1].push_back(0);
    indegree[1] = 1;
    for (int i=0;i<M;i++)
    {
        int s, t;
        cin >> s >> t;
        adj[s].push_back(t);
        inv_adj[t].push_back(s);
        indegree[t]++;
    }

    stack<int> st;
    st.push(0);
    memset(visited, 0, (N+1)*sizeof(int));
    visited[0] = 1;
    while (!st.empty()) {
        int v = st.top();
        st.pop();

        for (int i=0;i<adj[v].size();i++)
            if (!visited[adj[v][i]])
            {
                st.push(adj[v][i]);
                visited[adj[v][i]] = 1;
            }
    }

    if(!visited[N])
    {
        cout << 0 << endl;
        return 0;
    }

    for (int i=1;i<=N;i++)
    {
        if(!visited[i]){
            for (int j=0;j<adj[i].size();j++)
                indegree[adj[i][j]]--;
        }
    }

    int count = 0;
    stack<int> topo;

    for (int i=0;i<=N;i++)
    {
        int j;
        for (j=0;j<=N;j++)
            if (visited[j] && indegree[j] ==0)
                break;
        if (j > N)
        {
            cout << "INFINITE PATHS" << endl;
            return 0;
        }
        else
        {
            topo.push(j);
            ranks[count++] = j;
            if (j == N)
                break;

            indegree[j] = -1;
            for (int k=0;k<adj[j].size();k++)
                indegree[adj[j][k]]--;
        }
    }

    memset(total, 0, (N+1)*sizeof(long long));
    total[N] = 1;
    for (int i=count - 1;i>=0;i--)
    {
        int r = ranks[i];
        for (int j=0;j<inv_adj[r].size();j++)
            if(visited[inv_adj[r][j]])
            {
                total[inv_adj[r][j]] = (total[inv_adj[r][j]] + total[r]) % MODE;
            }
    }
    cout << total[0] << endl;
    return 0;
}

Answer 2

明显的错误。假设有一个循环，但是没有从循环到第二个城市的路径。然后你会说有无限多的路径，但是路径的数量实际上可能是有限的。

Answer 3

数字（3）（4）错误：

如果可以访问，则通过从节点0执行dfs来查找图中是否有任何循环。

如果存在循环，则打印无限路径

图中可能有一个循环，但如果无法从循环中访问目标，则所需的#路径仍然是有限的
示例：查找从A到C的#路径

A-->D<-->B
|
----->C

在这里：G=（V，E），V={A，B，C，D}和E={（D，B），（B，D），（A，C），（A，D）}

虽然有一个循环可从a（a）到达-

要查找从源到目标的路径中是否有循环，可以创建一个新的图，其中，原始图中有一条从V到目标的路径，并且可以创建一个新的图（仅减少到V的顶点），并在G上运行DFS/BFS。

还要注意的是，如果G中没有循环，那么根据定义，这是一个DAG，因此从现在开始处理G可能会简化查找路径的过程。（还必须修剪无法从源访问的顶点，以确保它确实是DAG）。