G - Return to 1 解説 by en_translator
First of all, the vertices not reachable from vertex \(1\) and those from which vertex \(1\) is not reachable (and the adjacent edges) can be removed from the graph. We now assume that the graph is strongly connected.
Let \(L\) be the set of sizes of lengths of cycles containing vertex \(1\), and \(G\) be the greatest common divisors of the numbers contained in \(L\) (or \(0\) if \(L\) is an empty set). Then, the answer is Yes if and only if \(G\) is a divisor of \(10^{10^{100}}\).
Proof
Suppose that there are two cycles of lengths $a$ and $b$. Also, suppose that $\gcd(a,b) = g$, where $a=ga'$ and $b=gb'$. Then, for all integers $k\geq a'b'$, there exist non-negative integers $x$ and $y$ such that $a'x+b'y=k$. Thus, by using the two cycles together, we can construct any cycle of a length that is a multiple of $\gcd(a,b)$ and is at least $\mathrm{lcm}(a,b)$. As an extension, by using $t$ cycles of lengths $l_1,l_2, \dots$, and $l_t$, we can construct any cycle of a length that is a multiple of $\gcd(l_1,l_2, \dots l_t)$ and is at least $\mathrm{lcm}(l_1,l_2, \dots l_t)$, which can be shown by induction. Since $10^{10^{100}}$ is sufficiently large, if $G$ is a divisor of $10^{10^{100}}$, then a cycle of length $10^{10^{100}}$ exists. Conversely, if $G$ has a prime divisor other than $2$ and $5$, then it is obvious that there is no cycle of a length that is a multiple of $10^{10^{100}}$. Thus, the proposition is proven.
However, \(L\) can be an infinite set, so we cannot find \(G\). Now, (it is a bit sudden) let us take an arbitrary directed spanning tree \(T\) rooted at vertex \(1\), and let \(d_i\) be the depth of vertex \(i\) in \(T\). Then, for all integers \(a\), the following fact holds:
\[ L\text{ contains an integer that is }\textbf{not}\text{ a multiple of }L \Leftrightarrow \text{there is an edge }u\rightarrow v\text{ such that } d_u+1-d_v \not\equiv 0 \pmod a. \]
Proof
($\Rightarrow$) We show the contraposition. Since $d_u+1 \equiv d_v \pmod a$ for all edges $u \rightarrow v$, the sequence of $d_i \bmod a$ on the cycle that starts from and ends at vertex $1$ is always periodic, like $0 \rightarrow 1 \rightarrow \dots \rightarrow a-1 \rightarrow 0 \rightarrow 1 \rightarrow \dots \rightarrow 0$. Thus, $l \bmod a \equiv 0$ for all $l \in L$.
($\Leftarrow$) Take a cycle that contains an edge such that $d_u+1-d_v \not\equiv 0 \pmod a$ exactly once, and let $l \in L$ be its length. (Since every edge in $T$ satisfies $d_u+1-d_v =0\equiv 0 \pmod a$, such a cycle always exists.) Then, $l \not\equiv 0 \pmod a$.
Hence, if we let \(G'\) be the greatest common divisor of \(|d_u+1-d_v|\) for all edges \(u \rightarrow v\), then \(G'\) coincides with \(g\). Since \(G\) can be found in a total of \(O(N+M)\) time, the problem has been solved.
Sample code (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';
}
}
投稿日時:
最終更新: