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

Question

王国连接

对于查尔斯国王来说，这是繁荣的一年，他正在迅速扩张他的王国。最近建造了一个美丽的新王国，在这个王国中有许多城市由多条单向道路连接。两个城市可能直接连接不止一条路，这是为了保证高连通性。

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

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

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

输入说明：

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

然后沿着M行，每行有两个整数x和y， 1<=x,y<=N ，表示从城市x到城市y有一条路。

输出说明：

打印从城市 1 到城市 N 的不同路径的数量以 1,000,000,000(10^9) 为模。如果有无限多不同的路径，则打印“INFINITE PATHS”（引号是为了清楚起见）。

样本输入：

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<=N<=10,000(10^4)

1<=M<=1,00,000(10^5)

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

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

检测节点 n 是否可以从节点 1 到达。
它不是那么所需的ans是0
如果其可达，则通过从节点 0 执行 dfs 来查找图中是否有任何循环
如果有循环，则打印 INFINITE PATHS
如果没有循环使用递归计算所需的ans
- F(n) = 1
- F(0) = Sumofall F(x) 使得 x 与 0 相邻
- 如果没有与 x 相邻的 x，则 F(x) = 0

我已将解决方案实施为：

#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");
}

我无法检测到这个算法的问题

score 4 · Accepted Answer

数字 (3)+(4) 错误：

如果其可达，则通过从节点 0 执行 dfs 来查找图中是否存在任何循环。

如果有循环，则打印 INFINITE PATHS

图中可能有一个循环，但如果从循环中无法到达目标，则所需的#paths 仍然是有限的数字。
示例：查找从 A 到 C 的#paths

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

在这里: G=(V,E),V = {A,B,C,D}和E = {(D,B),(B,D),(A,C),(A,D)}

虽然从 (A->D->B->D) 可以到达一个循环，但是从到的A路径只有一条。AC

要查找从源到目标的路径中是否存在循环，可以创建一个新图G'=(V',E')，其中V'= { v | there is a path in the original graph from v to target }和E' = V' x V' [intersection] E（E仅减少到的顶点V'），然后在上运行 DFS/BFS G'。

另请注意，如果没有循环-根据定义，G'它是一个DAGG' ，因此从现在开始工作可能会简化查找#paths。（您还必须修剪从源无法到达的顶点，以确保它确实是 DAG）。

score 2 · Accepted Answer

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

score 0 · Accepted Answer

你可以参考我的代码

#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;
}

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

3 回答 3

Related

Reference