algorithm - 2 つのノード間のパスの数を計算する

Question

王国のコネクティビティ

チャールズ国王にとって今年は繁栄の年であり、彼は王国を急速に拡大しています。最近、美しい新しい王国が建設され、この王国には多数の一方通行の道路で結ばれた多くの都市があります。2 つの都市は、複数の道路がある場合、これは高い接続性を確保するためです。

この新しい王国で、チャールズ王は都市の 1 つを彼の金融首都に、もう 1 つを戦争の首都にしました。彼はこれら 2 つの首都の間の高い接続性を望んでいます。都市 A と都市 B のペアの接続性は、都市 A から都市 B へのさまざまなパス。可能であれば、パスは道路を複数回使用する場合があります。まったく同じ一連の道路を使用しない場合、2 つのパスは異なるものと見なされます。

新しい王国には 1 から N までの番号が付けられた N 個の都市と、一方通行の M 本の道路があります。都市 1 は通貨の首都であり、都市 N は戦争の首都です。

新しい王国で最高のプログラマーの 1 人であるあなたは、金融資本と戦争資本の接続性、つまり都市 1 から都市 N へのさまざまなパスの数に答える必要があります。

入力の説明:

最初の行には、2 つの整数 N と M が含まれています。

次に、それぞれが x と y という 2 つの整数 (1<=x,y<=N) を持つ M 行をたどります。これは、都市 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)

2 つの都市は 3 つ以上の道路で接続されている場合があり、その場合、それらの道路は異なるパスをカウントするために異なるものと見なされます。

問題を解決するために使用するアルゴリズムは次のとおりです。

ノード n がノード 1 から到達可能かどうかを検出します。
その場合、必要な ans は 0 ではありません
到達可能な場合は、ノード 0 から dfs を実行して、グラフにサイクルがあるかどうかを確認します
サイクルがある場合は、INFINITE PATHS を出力します。
サイクルがない場合は、繰り返しを使用して必要な ans を計算します
- F(n) = 1
- F(0) = x が 0 に隣接する Sumofall F(x)
- 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 への #path を探す

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のパスは 1 つしかありません。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

明らかな間違い。サイクルがあるとしますが、サイクルから 2 番目の都市への道はありません。無限の数の経路があると言うでしょうが、経路の数は実際には有限かもしれません。

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 - 2 つのノード間のパスの数を計算する

3 に答える 3

Related

Reference