王国のコネクティビティ
チャールズ国王にとって今年は繁栄の年であり、彼は王国を急速に拡大しています。最近、美しい新しい王国が建設され、この王国には多数の一方通行の道路で結ばれた多くの都市があります。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");
}
このアルゴリズムの問題を検出できません