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

View this file on GitHub
Last update: 2026-10-11 23:34:07+09:00
Include: #include "src/graph/functional-graph.hpp"

$n$ 頂点 $n$ 辺で、すべての頂点の出次数が 1 の有向グラフ (頂点 $i$ から $g_i$ への辺) です。各連結成分はサイクル 1 つと、そこに流れ込む木からなります。

FunctionalGraph fg(std::vector<int>{1, 2, 0, 0, 3});  // 0→1→2→0 のサイクルに 4→3→0 が流れ込む
int v = fg.hop(4, 10);       // 4 から 10 回移動した頂点: 2
int c = fg.hopable(4);       // 4 から到達できる頂点の個数: 5
bool b = fg.is_cycle[3];     // false

FunctionalGraph(n) で作った場合は、read() で入力するまで前計算が行われません。

メンバ関数

関数	説明	計算量
`FunctionalGraph(g)`	頂点 `i` から `g[i]` への辺を持つグラフを作る	$O(n \log n)$
`FunctionalGraph(n)` + `read(padding = -1)`	標準入力から `g[0], ..., g[n-1]` を読む。頂点番号に `padding` を足す	$O(n \log n)$
`hop(x, k)`	`x` から `k` 回移動した頂点 (`k` は `long long` でよい)	$O(\log n)$
`hopable(x)`	`x` から 0 回以上の移動で到達できる頂点の個数	$O(1)$

メンバ変数

変数	内容
`n` / `g`	頂点数 / 各頂点の行き先
`is_cycle[v]`	`v` がサイクル上にあるか
`depth[v]`	`v` からサイクルに入るまでの距離 (サイクル上なら 0)
`root[v]`	`v` から進んで最初に着くサイクル上の頂点
`connected_id[v]`	`v` が属する連結成分の番号
`connected_list[c]`	連結成分 `c` の頂点のリスト
`cycle_list[c]`	連結成分 `c` のサイクルの頂点を、辺をたどる順に並べたリスト
`root_idx[v]`	`root[v]` の `cycle_list` 上の位置

Verified with

Code

#pragma once

/**
 * @file functional-graph.hpp
 * @brief ファンクショナルグラフ
 */
#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>

/**
 * @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 2 "src/graph/functional-graph.hpp"

/**
 * @file functional-graph.hpp
 * @brief ファンクショナルグラフ
 */
#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>

/**
 * @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();
    }
};

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

メンバ関数

メンバ変数

Verified with

Code

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