library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unit/functional_graph.test.cpp
- View this file on GitHub
- Last update: 2026-10-22 22:21:08+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>
#include "graph/functional_graph.hpp"
int main() {
std::mt19937 rng(12345);
for (int it = 0; it < 3000; it++) {
int n = 1 + rng() % 12;
std::vector<int> f(n);
for (int& x : f) x = rng() % n;
if (rng() % 3 == 0) {
// permutation
for (int i = 0; i < n; i++) f[i] = i;
std::shuffle(f.begin(), f.end(), rng);
}
functional_graph g(f);
// naive: walk from v, find depth (first repeated vertex) and cycle
std::vector<int> naive_root(n), naive_depth(n);
std::vector<std::vector<int>> naive_cycle(n);
for (int v = 0; v < n; v++) {
std::vector<int> seen(n, -1), path;
int u = v, step = 0;
while (seen[u] == -1) {
seen[u] = step++;
path.push_back(u);
u = f[u];
}
naive_depth[v] = seen[u];
naive_root[v] = u;
naive_cycle[v] = std::vector<int>(path.begin() + seen[u], path.end());
}
int total_cycle_vertices = 0;
for (int v = 0; v < n; v++) {
assert(g.root(v) == naive_root[v]);
assert(g.depth(v) == naive_depth[v]);
assert(g.on_cycle(v) == (naive_depth[v] == 0));
total_cycle_vertices += g.on_cycle(v);
// cycle(v) is a rotation of naive_cycle[v]
const std::vector<int>& c = g.cycle(v);
assert(c.size() == naive_cycle[v].size());
int k = int(c.size());
int off = int(std::find(c.begin(), c.end(), naive_cycle[v][0]) - c.begin());
assert(off < k);
for (int i = 0; i < k; i++) assert(c[(off + i) % k] == naive_cycle[v][i]);
for (int i = 0; i < k; i++) assert(f[c[i]] == c[(i + 1) % k]);
// component ids agree with root's cycle
assert(g.component(v) == g.component(g.root(v)));
assert(&g.cycles()[g.component(v)] == &g.cycle(v));
// jump
for (long long step : {0LL, 1LL, 2LL, 3LL, 5LL, 7LL, 12LL, 13LL, 1000000000000000000LL}) {
int u = v;
long long s = step;
if (s > 50) {
// reduce using cycle length after reaching cycle
int d = naive_depth[v];
for (int i = 0; i < d; i++) u = f[u];
long long rem = (s - d) % (long long)naive_cycle[v].size();
for (int i = 0; i < rem; i++) u = f[u];
} else {
for (int i = 0; i < s; i++) u = f[u];
}
assert(g.jump(v, step) == u);
}
}
int cyc_sum = 0;
for (const std::vector<int>& c : g.cycles()) cyc_sum += int(c.size());
assert(cyc_sum == total_cycle_vertices);
// children: reverse edges excluding cycle edges
std::vector<std::set<int>> ch(n);
for (int v = 0; v < n; v++) {
if (!g.on_cycle(v)) ch[f[v]].insert(v);
}
for (int v = 0; v < n; v++) {
std::set<int> got(g.children(v).begin(), g.children(v).end());
assert(got == ch[v]);
assert(got.size() == g.children(v).size());
}
}
std::cout << "Hello World" << std::endl;
}#line 1 "test/unit/functional_graph.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>
#line 2 "graph/functional_graph.hpp"
#include <bit>
#line 5 "graph/functional_graph.hpp"
struct functional_graph {
public:
functional_graph() : functional_graph(std::vector<int>()) {
}
explicit functional_graph(std::vector<int> f)
: _n(int(f.size())),
_f(std::move(f)),
_root(_n, -1),
_depth(_n, 0),
_component(_n, -1),
_pos(_n, -1),
_children(_n) {
for (int v = 0; v < _n; v++) assert(0 <= _f[v] && _f[v] < _n);
std::vector<int> state(_n, 0);
for (int s = 0; s < _n; s++) {
if (state[s]) continue;
int v = s;
while (state[v] == 0) {
state[v] = 1;
v = _f[v];
}
if (state[v] == 1) {
int k = int(_cycles.size());
std::vector<int> cyc;
int u = v;
do {
cyc.push_back(u);
_root[u] = u;
_component[u] = k;
_pos[u] = int(cyc.size()) - 1;
u = _f[u];
} while (u != v);
_cycles.push_back(std::move(cyc));
}
for (int u = s; state[u] == 1; u = _f[u]) state[u] = 2;
}
for (int v = 0; v < _n; v++) {
if (_root[v] != v) _children[_f[v]].push_back(v);
}
std::vector<int> order;
order.reserve(_n);
for (const std::vector<int>& cyc : _cycles) {
for (int v : cyc) order.push_back(v);
}
int max_depth = 0;
for (int i = 0; i < _n; i++) {
int v = order[i];
for (int c : _children[v]) {
_root[c] = _root[v];
_depth[c] = _depth[v] + 1;
_component[c] = _component[v];
order.push_back(c);
if (max_depth < _depth[c]) max_depth = _depth[c];
}
}
int log = std::bit_width((unsigned)max_depth);
_up.assign(log, std::vector<int>(_n));
for (int j = 0; j < log; j++) {
for (int v = 0; v < _n; v++) {
_up[j][v] = j == 0 ? _f[v] : _up[j - 1][_up[j - 1][v]];
}
}
}
int jump(int v, long long k) const {
assert(0 <= v && v < _n);
assert(0 <= k);
if (k < _depth[v]) {
for (int j = 0; k; j++, k >>= 1) {
if (k & 1) v = _up[j][v];
}
return v;
}
k -= _depth[v];
const std::vector<int>& cyc = _cycles[_component[v]];
int len = int(cyc.size());
return cyc[(_pos[_root[v]] + k % len) % len];
}
bool on_cycle(int v) const {
assert(0 <= v && v < _n);
return _root[v] == v;
}
int root(int v) const {
assert(0 <= v && v < _n);
return _root[v];
}
int depth(int v) const {
assert(0 <= v && v < _n);
return _depth[v];
}
int component(int v) const {
assert(0 <= v && v < _n);
return _component[v];
}
const std::vector<int>& cycle(int v) const {
assert(0 <= v && v < _n);
return _cycles[_component[v]];
}
const std::vector<std::vector<int>>& cycles() const {
return _cycles;
}
const std::vector<int>& children(int v) const {
assert(0 <= v && v < _n);
return _children[v];
}
private:
int _n;
std::vector<int> _f, _root, _depth, _component, _pos;
std::vector<std::vector<int>> _children, _cycles, _up;
};
#line 10 "test/unit/functional_graph.test.cpp"
int main() {
std::mt19937 rng(12345);
for (int it = 0; it < 3000; it++) {
int n = 1 + rng() % 12;
std::vector<int> f(n);
for (int& x : f) x = rng() % n;
if (rng() % 3 == 0) {
// permutation
for (int i = 0; i < n; i++) f[i] = i;
std::shuffle(f.begin(), f.end(), rng);
}
functional_graph g(f);
// naive: walk from v, find depth (first repeated vertex) and cycle
std::vector<int> naive_root(n), naive_depth(n);
std::vector<std::vector<int>> naive_cycle(n);
for (int v = 0; v < n; v++) {
std::vector<int> seen(n, -1), path;
int u = v, step = 0;
while (seen[u] == -1) {
seen[u] = step++;
path.push_back(u);
u = f[u];
}
naive_depth[v] = seen[u];
naive_root[v] = u;
naive_cycle[v] = std::vector<int>(path.begin() + seen[u], path.end());
}
int total_cycle_vertices = 0;
for (int v = 0; v < n; v++) {
assert(g.root(v) == naive_root[v]);
assert(g.depth(v) == naive_depth[v]);
assert(g.on_cycle(v) == (naive_depth[v] == 0));
total_cycle_vertices += g.on_cycle(v);
// cycle(v) is a rotation of naive_cycle[v]
const std::vector<int>& c = g.cycle(v);
assert(c.size() == naive_cycle[v].size());
int k = int(c.size());
int off = int(std::find(c.begin(), c.end(), naive_cycle[v][0]) - c.begin());
assert(off < k);
for (int i = 0; i < k; i++) assert(c[(off + i) % k] == naive_cycle[v][i]);
for (int i = 0; i < k; i++) assert(f[c[i]] == c[(i + 1) % k]);
// component ids agree with root's cycle
assert(g.component(v) == g.component(g.root(v)));
assert(&g.cycles()[g.component(v)] == &g.cycle(v));
// jump
for (long long step : {0LL, 1LL, 2LL, 3LL, 5LL, 7LL, 12LL, 13LL, 1000000000000000000LL}) {
int u = v;
long long s = step;
if (s > 50) {
// reduce using cycle length after reaching cycle
int d = naive_depth[v];
for (int i = 0; i < d; i++) u = f[u];
long long rem = (s - d) % (long long)naive_cycle[v].size();
for (int i = 0; i < rem; i++) u = f[u];
} else {
for (int i = 0; i < s; i++) u = f[u];
}
assert(g.jump(v, step) == u);
}
}
int cyc_sum = 0;
for (const std::vector<int>& c : g.cycles()) cyc_sum += int(c.size());
assert(cyc_sum == total_cycle_vertices);
// children: reverse edges excluding cycle edges
std::vector<std::set<int>> ch(n);
for (int v = 0; v < n; v++) {
if (!g.on_cycle(v)) ch[f[v]].insert(v);
}
for (int v = 0; v < n; v++) {
std::set<int> got(g.children(v).begin(), g.children(v).end());
assert(got == ch[v]);
assert(got.size() == g.children(v).size());
}
}
std::cout << "Hello World" << std::endl;
}