test/unittest/functional-graph.test.cpp

• View this file on GitHub
• Last update: 2026-10-12 00:13:34+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• ファンクショナルグラフ (src/graph/functional-graph.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

// FunctionalGraph を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <algorithm>
#include <iostream>
#include <random>
#include <set>
#include <vector>

#include "../../src/graph/functional-graph.hpp"

// x から k 回移動した頂点 (周期を見つけて k を縮める)
int naive_hop(const std::vector<int>& g, int x, long long k) {
    std::vector<long long> visited(g.size(), -1);
    for (long long t = 0; t < k; t++) {
        if (visited[x] != -1) {
            long long period = t - visited[x];
            long long rest = (k - t) % period;
            for (long long i = 0; i < rest; i++) x = g[x];
            return x;
        }
        visited[x] = t;
        x = g[x];
    }
    return x;
}

int main() {
    std::mt19937_64 rng(314);
    bool ok = true;
    for (int rep = 0; rep < 3000 && ok; rep++) {
        int n = rng() % 12 + 1;
        std::vector<int> g(n);
        for (int& v : g) v = rng() % n;
        FunctionalGraph fg(g);

        // サイクル上の頂点: ある 1 <= j <= n で g^j(x) = x
        std::vector<bool> on_cycle(n);
        for (int x = 0; x < n; x++) {
            int y = x;
            for (int j = 0; j < n; j++) {
                y = g[y];
                if (y == x) on_cycle[x] = true;
            }
        }
        // cycle_list の各要素は g でつながったサイクルで、全体としてサイクル上の頂点をちょうど1回ずつ含む
        std::vector<int> cnt(n);
        for (const auto& cycle : fg.cycle_list) {
            for (int i = 0; i < (int)cycle.size(); i++) {
                if (g[cycle[i]] != cycle[(i + 1) % cycle.size()]) ok = false;
                cnt[cycle[i]]++;
            }
        }
        for (int x = 0; x < n; x++) {
            if (cnt[x] != (on_cycle[x] ? 1 : 0)) ok = false;
            if (fg.is_cycle[x] != on_cycle[x]) ok = false;
        }

        for (int x = 0; x < n; x++) {
            // hopable: 0 回以上の移動でたどり着ける頂点の個数
            std::set<int> reach;
            int y = x;
            for (int j = 0; j <= n; j++) {
                reach.insert(y);
                y = g[y];
            }
            if (fg.hopable(x) != (int)reach.size()) ok = false;
            // hop: 小さい k と大きい k
            for (long long k = 0; k <= 3 * n; k++) {
                if (fg.hop(x, k) != naive_hop(g, x, k)) ok = false;
            }
            long long k = rng() % 1000000000000000000LL;
            if (fg.hop(x, k) != naive_hop(g, x, k)) ok = false;
        }
    }
    if (ok) std::cout << "Hello World" << std::endl;
}

#line 1 "test/unittest/functional-graph.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"

// FunctionalGraph を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する

#include <algorithm>
#include <iostream>
#include <random>
#include <set>
#include <vector>

#line 2 "src/graph/functional-graph.hpp"

/**
 * @file functional-graph.hpp
 * @brief ファンクショナルグラフ
 */
#line 9 "src/graph/functional-graph.hpp"
#include <numeric>
#line 12 "src/graph/functional-graph.hpp"

/**
 * @brief N頂点N辺の有向グラフで、すべての頂点の出次数が1
 */
struct FunctionalGraph {
    int n;                                         //!< 頂点数
    std::vector<int> g;                            //!< グラフ
    std::vector<bool> is_cycle;                    //!< サイクル上の頂点か
    std::vector<int> depth;                        //!< サイクル上の頂点までの距離
    std::vector<int> root;                         //!< 最も近いサイクル上の頂点
    std::vector<std::vector<int>> connected_list;  //!< 各連結成分のリスト
    std::vector<std::vector<int>> cycle_list;      //!< 各連結成分のサイクル
    std::vector<int> connected_id;                 //!< その頂点が属する連結成分のindex
    std::vector<int> root_idx;                     //!< rootのcycle_list上のindex
    std::vector<std::vector<int>> doubling;        //!< DoublingClimbTree

    void build() {
        is_cycle.assign(n, false);
        depth.assign(n, 0);
        root.assign(n, -1);
        connected_id.assign(n, 0);
        root_idx.assign(n, 0);
        connected_list.clear();
        cycle_list.clear();
        std::vector<bool> visited(n);
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            std::vector<int> v;
            int u = i;
            while (!visited[u]) {
                visited[u] = true;
                v.push_back(u);
                u = g[u];
            }
            if (root[u] == -1) {
                int k = std::find(v.begin(), v.end(), u) - v.begin();
                cycle_list.push_back({});
                connected_list.push_back({});
                for (int j = 0; j < k; j++) {
                    is_cycle[v[j]] = false;
                    root[v[j]] = u;
                    root_idx[v[j]] = 0;
                    connected_id[v[j]] = cycle_list.size() - 1;
                    depth[v[j]] = k - j;
                    connected_list.back().push_back(v[j]);
                }
                for (int j = k; j < (int)v.size(); j++) {
                    is_cycle[v[j]] = true;
                    root[v[j]] = v[j];
                    cycle_list.back().push_back(v[j]);
                    root_idx[v[j]] = cycle_list.back().size() - 1;
                    connected_id[v[j]] = cycle_list.size() - 1;
                    depth[v[j]] = 0;
                    connected_list.back().push_back(v[j]);
                }
            } else {
                for (int j = 0; j < (int)v.size(); j++) {
                    is_cycle[v[j]] = false;
                    root[v[j]] = root[u];
                    root_idx[v[j]] = root_idx[u];
                    connected_id[v[j]] = connected_id[u];
                    depth[v[j]] = depth[u] + v.size() - j;
                    connected_list[connected_id[u]].push_back(v[j]);
                }
            }
        }
        doubling.assign(n, {});
        std::vector<int> tmp;
        for (int i = 0; i < n; i++) {
            if (is_cycle[i]) continue;
            tmp.push_back(i);
            doubling[i].push_back(g[i]);
        }
        for (int k = 0; !tmp.empty(); k++) {
            std::vector<int> next_tmp;
            for (int i : tmp) {
                if (k < (int)doubling[doubling[i][k]].size()) {
                    doubling[i].push_back(doubling[doubling[i][k]][k]);
                    next_tmp.push_back(i);
                }
            }
            tmp.swap(next_tmp);
        }
    }

    /**
     * @brief デフォルトコンストラクタ
     */
    FunctionalGraph() : n(0), g(0) {}
    /**
     * @brief コンストラクタ
     * @param n 頂点数
     */
    explicit FunctionalGraph(int n) : n(n), g(n) {}
    /**
     * @brief コンストラクタ
     * @param g i -> g[i]
     */
    explicit FunctionalGraph(std::vector<int> g) : n(g.size()), g(g) {
        build();
    }
    /**
     * @brief 辺の情報を標準入力から受け取って追加する
     * @param padding 頂点番号を入力からいくつずらすか 省略したら-1
     */
    void read(int padding = -1) {
        for (int i = 0; i < n; i++) {
            std::cin >> g[i];
            g[i] += padding;
        }
        build();
    }
    /**
     * @brief 頂点xからk回移動した頂点
     *
     * @param x 0 <= x < n
     * @param k 0 <= k
     * @return int 頂点番号
     */
    int hop(int x, long long k) const {
        if (k >= depth[x]) {
            k -= depth[x];
            x = root[x];
            k %= cycle_list[connected_id[x]].size();
            int y = root_idx[x] + k;
            if ((int)cycle_list[connected_id[x]].size() <= y) {
                y -= cycle_list[connected_id[x]].size();
            }
            return cycle_list[connected_id[x]][y];
        }
        for (int i = 0; k; i++) {
            if (k & 1) {
                x = doubling[x][i];
            }
            k >>= 1;
        }
        return x;
    }
    /**
     * @brief 頂点xから0回以上の移動でたどり着ける頂点の個数
     */
    int hopable(int x) const {
        return depth[x] + (int)cycle_list[connected_id[x]].size();
    }
};
#line 13 "test/unittest/functional-graph.test.cpp"

// x から k 回移動した頂点 (周期を見つけて k を縮める)
int naive_hop(const std::vector<int>& g, int x, long long k) {
    std::vector<long long> visited(g.size(), -1);
    for (long long t = 0; t < k; t++) {
        if (visited[x] != -1) {
            long long period = t - visited[x];
            long long rest = (k - t) % period;
            for (long long i = 0; i < rest; i++) x = g[x];
            return x;
        }
        visited[x] = t;
        x = g[x];
    }
    return x;
}

int main() {
    std::mt19937_64 rng(314);
    bool ok = true;
    for (int rep = 0; rep < 3000 && ok; rep++) {
        int n = rng() % 12 + 1;
        std::vector<int> g(n);
        for (int& v : g) v = rng() % n;
        FunctionalGraph fg(g);

        // サイクル上の頂点: ある 1 <= j <= n で g^j(x) = x
        std::vector<bool> on_cycle(n);
        for (int x = 0; x < n; x++) {
            int y = x;
            for (int j = 0; j < n; j++) {
                y = g[y];
                if (y == x) on_cycle[x] = true;
            }
        }
        // cycle_list の各要素は g でつながったサイクルで、全体としてサイクル上の頂点をちょうど1回ずつ含む
        std::vector<int> cnt(n);
        for (const auto& cycle : fg.cycle_list) {
            for (int i = 0; i < (int)cycle.size(); i++) {
                if (g[cycle[i]] != cycle[(i + 1) % cycle.size()]) ok = false;
                cnt[cycle[i]]++;
            }
        }
        for (int x = 0; x < n; x++) {
            if (cnt[x] != (on_cycle[x] ? 1 : 0)) ok = false;
            if (fg.is_cycle[x] != on_cycle[x]) ok = false;
        }

        for (int x = 0; x < n; x++) {
            // hopable: 0 回以上の移動でたどり着ける頂点の個数
            std::set<int> reach;
            int y = x;
            for (int j = 0; j <= n; j++) {
                reach.insert(y);
                y = g[y];
            }
            if (fg.hopable(x) != (int)reach.size()) ok = false;
            // hop: 小さい k と大きい k
            for (long long k = 0; k <= 3 * n; k++) {
                if (fg.hop(x, k) != naive_hop(g, x, k)) ok = false;
            }
            long long k = rng() % 1000000000000000000LL;
            if (fg.hop(x, k) != naive_hop(g, x, k)) ok = false;
        }
    }
    if (ok) std::cout << "Hello World" << std::endl;
}

Back to top page