G - Return to 1 Editorial by yuto1115
解説まず、頂点 \(1\) から到達できない頂点および頂点 \(1\) に到達できない頂点（とそれらに繋がる辺）はグラフから削除してしまって問題ありません。以下、グラフ全体が強連結であることを仮定します。
頂点 \(1\) を含むサイクルの長さの集合を \(L\) とし、\(L\) に含まれる数の最大公約数を \(G\) （\(L\) が空集合の場合は \(G=0\)）とします。このとき、答えが Yes になるための必要十分条件は \(G\) が \(10^{10^{100}}\) の約数であることです。
証明
長さがそれぞれ $a,b$ である $2$ つのサイクルがあったとします。また、$\gcd(a,b) = g,a=ga',b=gb'$ であるとします。このとき、$k\geq a'b'$ を満たす全ての $k$ について $a'x+b'y=k$ を満たす非負整数 $x,y$ が存在することから、$2$ つのサイクルを組み合わせることで、$\gcd(a,b)$ の倍数かつ $\mathrm{lcm}(a,b)$ 以上の長さであるサイクルは全て作ることができます。これを拡張すると、長さが $l_1,l_2, \dots l_t$ である $t$ 個のサイクルを組み合わせることで、 $\gcd(l_1,l_2, \dots l_t)$ の倍数かつ $\mathrm{lcm}(l_1,l_2, \dots l_t)$ 以上の長さであるサイクルは全て作れることを数学的帰納法により示せます。$10^{10^{100}}$ は十分大きいですから、 $G$ が $10^{10^{100}}$ の約数ならば長さが $10^{10^{100}}$ であるサイクルが存在することがわかります。逆に、$G$ が $2,5$ 以外の素因数 $p$ を含むならば、長さが $10^{10^{100}}$ であるサイクルが存在しないことは明らかです。よって示されました。
しかし、\(L\) は無限集合になることもあり、このままでは \(G\) を求めることができません。そこで、（唐突ですが）頂点 \(1\) を根とする適当な全域有向木 \(T\) を取り、\(T\) 上での頂点 \(i\) の深さを \(d_i\) とします。すると、任意の正整数 \(a\) について以下の事実が成り立ちます。
\[ a\text{ の倍数}\textbf{でない}\text{数が }L\text{ に含まれる} \Leftrightarrow d_u+1-d_v \not\equiv 0 \pmod a \text{ を満たす辺 } u\rightarrow v\text{ が存在する} \]
証明
($\Rightarrow$) 対偶を示します。 全ての辺 $u \rightarrow v$ について $d_u+1 \equiv d_v \pmod a$ より、頂点 $1$ からスタートして頂点 $1$ に戻ってくるようなサイクル上の $d_i \bmod a$ の値を訪問順に並べると、必ず $0 \rightarrow 1 \rightarrow \dots \rightarrow a-1 \rightarrow 0 \rightarrow 1 \rightarrow \dots \rightarrow 0$ というように周期的に変化します。よって、全ての $l \in L$ について $l \bmod a \equiv 0$ です。
($\Leftarrow$) $d_u+1-d_v \not\equiv 0 \pmod a$ を満たす辺をちょうど $1$ つだけ含むようなサイクルを $1$ つ取り、その長さを $l \in L$ とします（$T$ に含まれる辺は $d_u+1-d_v =0\equiv 0 \pmod a$ であることから、そのようなサイクルは必ず存在します）。このとき、$l \not\equiv 0 \pmod a$ です。
ゆえに、全ての辺 \(u \rightarrow v\) に対する \(|d_u+1-d_v|\) の最大公約数を \(G'\)（辺が存在しない場合は \(G'=0\)）とすると、\(G'\) は \(g\) に一致します。\(G'\) は \(O(N+M)\) で求められるので、この問題を解くことができました。
実装例 (C++) :
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<vector<int>> G(n), rG(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
--u, --v;
G[u].push_back(v);
rG[v].push_back(u);
}
vector<int> dep(n, -1);
dep[0] = 0;
auto dfs = [&](auto &dfs, int u) -> void {
for (int v: G[u]) {
if (dep[v] != -1) continue;
dep[v] = dep[u] + 1;
dfs(dfs, v);
}
};
dfs(dfs, 0);
vector<bool> valid(n); // valid[i] = i から 0 に到達可能かどうか
auto dfs_r = [&](auto &dfs_r, int u) -> void {
valid[u] = true;
for (int v: rG[u]) {
if (valid[v]) continue;
dfs_r(dfs_r, v);
}
};
dfs_r(dfs_r, 0);
for (int i = 0; i < n; i++) if (!valid[i]) dep[i] = -1;
int g = 0;
for (int u = 0; u < n; u++) {
if (dep[u] == -1) continue;
for (int v: G[u]) {
if (dep[v] == -1) continue;
g = gcd(g, abs(dep[u] + 1 - dep[v]));
}
}
if (!g) {
cout << "No\n";
continue;
}
while (g % 2 == 0) g /= 2;
while (g % 5 == 0) g /= 5;
cout << (g == 1 ? "Yes" : "No") << '\n';
}
}
posted:
last update: