Functional Graph
(graph/functional_graph.cpp)

• View this file on GitHub
• Last update: 2026-03-23 22:54:37+09:00

説明

各頂点の出次数が 1 の有向グラフを扱う。 cycle 分解と doubling を前計算し、k 個先の頂点と各頂点が属する閉路情報を取る。 前処理 $O(N \log K)$、jump は $O(\log K)$、それ以外は $O(1)$。

できること

• FunctionalGraph fg(n) n 頂点の関数グラフを作る
• FunctionalGraph fg(to) 遷移先配列 to から作ってそのまま build する
• void set_edge(int v, int nxt) v -> nxt を設定する
• void build() 閉路分解と doubling を前計算する
• int jump(int v, long long k) v から k 回遷移した先を返す
• bool in_cycle(int v) v が閉路上なら true
• int cycle_id(int v) v が属する連結成分の閉路 id を返す
• int cycle_size(int v) v が流れ込む閉路の長さを返す
• int steps_to_cycle(int v) v から閉路に入るまでの遷移回数を返す
• int cycle_vertex(int v) v から進んで最初に到達する閉路頂点を返す
• int cycle_index(int v) cycle_vertex(v) の閉路内 index を返す
• const vector<int> &cycle(int id) 閉路 id の頂点列を返す。辺の向き順に並ぶ

使い方

各頂点の遷移先を set_edge で入れてから build() を呼ぶ。 jump(v, k) で k 個先を求め、steps_to_cycle(v) や cycle_size(v) で構造情報を使う。

FunctionalGraph fg(n);
for (int v = 0; v < n; ++v) {
    fg.set_edge(v, to[v]);
}
fg.build();

int x = fg.jump(v, k);
int len = fg.cycle_size(v);

実装上の補足

• cycle(id) の先頭は実装依存だが、並び順は常に遷移先方向にそろう
• cycle_index(v) は非閉路頂点でも使え、cycle_vertex(v) の位置を返す

Verified with

• test/yosupo_aplusb_functional_graph.test.cpp

Code

struct FunctionalGraph {
    static constexpr int LOG = 63;

    int n;
    vector<int> to;
    vector<vector<int>> up;
    vector<int> comp_id;
    vector<int> cycle_pos;
    vector<int> cycle_len;
    vector<int> dist_to_cycle;
    vector<int> cycle_entry;
    vector<vector<int>> cycles;

    explicit FunctionalGraph(int n)
        : n(n),
          to(n, -1),
          up(LOG, vector<int>(n, -1)),
          comp_id(n, -1),
          cycle_pos(n, -1),
          cycle_len(n, 0),
          dist_to_cycle(n, -1),
          cycle_entry(n, -1) {}

    explicit FunctionalGraph(const vector<int> &to)
        : FunctionalGraph((int)to.size()) {
        this->to = to;
        build();
    }

    void set_edge(int v, int nxt) {
        to[v] = nxt;
    }

    void build() {
        up.assign(LOG, vector<int>(n, -1));
        for (int v = 0; v < n; ++v) up[0][v] = to[v];
        for (int k = 0; k + 1 < LOG; ++k) {
            for (int v = 0; v < n; ++v) {
                up[k + 1][v] = up[k][up[k][v]];
            }
        }

        vector<int> indeg(n);
        for (int v = 0; v < n; ++v) ++indeg[to[v]];

        vector<int> que, order;
        que.reserve(n);
        order.reserve(n);
        for (int v = 0; v < n; ++v) {
            if (indeg[v] == 0) que.push_back(v);
        }
        for (int head = 0; head < (int)que.size(); ++head) {
            int v = que[head];
            order.push_back(v);
            int nxt = to[v];
            if (--indeg[nxt] == 0) que.push_back(nxt);
        }

        comp_id.assign(n, -1);
        cycle_pos.assign(n, -1);
        cycle_len.assign(n, 0);
        dist_to_cycle.assign(n, -1);
        cycle_entry.assign(n, -1);
        cycles.clear();

        vector<int> seen(n);
        for (int v = 0; v < n; ++v) {
            if (indeg[v] == 0 || seen[v]) continue;
            int cid = cycles.size();
            vector<int> cyc;
            int cur = v;
            do {
                seen[cur] = 1;
                comp_id[cur] = cid;
                cycle_pos[cur] = cyc.size();
                dist_to_cycle[cur] = 0;
                cycle_entry[cur] = cur;
                cyc.push_back(cur);
                cur = to[cur];
            } while (cur != v);
            for (int x : cyc) cycle_len[x] = cyc.size();
            cycles.push_back(cyc);
        }

        for (int i = (int)order.size() - 1; i >= 0; --i) {
            int v = order[i];
            int nxt = to[v];
            comp_id[v] = comp_id[nxt];
            cycle_pos[v] = cycle_pos[nxt];
            cycle_len[v] = cycle_len[nxt];
            dist_to_cycle[v] = dist_to_cycle[nxt] + 1;
            cycle_entry[v] = cycle_entry[nxt];
        }
    }

    int jump(int v, long long k) const {
        for (int i = 0; i < LOG; ++i) {
            if ((k >> i) & 1) v = up[i][v];
        }
        return v;
    }

    bool in_cycle(int v) const {
        return dist_to_cycle[v] == 0;
    }

    int cycle_id(int v) const {
        return comp_id[v];
    }

    int cycle_size(int v) const {
        return cycle_len[v];
    }

    int steps_to_cycle(int v) const {
        return dist_to_cycle[v];
    }

    int cycle_vertex(int v) const {
        return cycle_entry[v];
    }

    int cycle_index(int v) const {
        return cycle_pos[v];
    }

    const vector<int> &cycle(int id) const {
        return cycles[id];
    }
};

/**
 * @brief Functional Graph
 */

#line 1 "graph/functional_graph.cpp"
struct FunctionalGraph {
    static constexpr int LOG = 63;

    int n;
    vector<int> to;
    vector<vector<int>> up;
    vector<int> comp_id;
    vector<int> cycle_pos;
    vector<int> cycle_len;
    vector<int> dist_to_cycle;
    vector<int> cycle_entry;
    vector<vector<int>> cycles;

    explicit FunctionalGraph(int n)
        : n(n),
          to(n, -1),
          up(LOG, vector<int>(n, -1)),
          comp_id(n, -1),
          cycle_pos(n, -1),
          cycle_len(n, 0),
          dist_to_cycle(n, -1),
          cycle_entry(n, -1) {}

    explicit FunctionalGraph(const vector<int> &to)
        : FunctionalGraph((int)to.size()) {
        this->to = to;
        build();
    }

    void set_edge(int v, int nxt) {
        to[v] = nxt;
    }

    void build() {
        up.assign(LOG, vector<int>(n, -1));
        for (int v = 0; v < n; ++v) up[0][v] = to[v];
        for (int k = 0; k + 1 < LOG; ++k) {
            for (int v = 0; v < n; ++v) {
                up[k + 1][v] = up[k][up[k][v]];
            }
        }

        vector<int> indeg(n);
        for (int v = 0; v < n; ++v) ++indeg[to[v]];

        vector<int> que, order;
        que.reserve(n);
        order.reserve(n);
        for (int v = 0; v < n; ++v) {
            if (indeg[v] == 0) que.push_back(v);
        }
        for (int head = 0; head < (int)que.size(); ++head) {
            int v = que[head];
            order.push_back(v);
            int nxt = to[v];
            if (--indeg[nxt] == 0) que.push_back(nxt);
        }

        comp_id.assign(n, -1);
        cycle_pos.assign(n, -1);
        cycle_len.assign(n, 0);
        dist_to_cycle.assign(n, -1);
        cycle_entry.assign(n, -1);
        cycles.clear();

        vector<int> seen(n);
        for (int v = 0; v < n; ++v) {
            if (indeg[v] == 0 || seen[v]) continue;
            int cid = cycles.size();
            vector<int> cyc;
            int cur = v;
            do {
                seen[cur] = 1;
                comp_id[cur] = cid;
                cycle_pos[cur] = cyc.size();
                dist_to_cycle[cur] = 0;
                cycle_entry[cur] = cur;
                cyc.push_back(cur);
                cur = to[cur];
            } while (cur != v);
            for (int x : cyc) cycle_len[x] = cyc.size();
            cycles.push_back(cyc);
        }

        for (int i = (int)order.size() - 1; i >= 0; --i) {
            int v = order[i];
            int nxt = to[v];
            comp_id[v] = comp_id[nxt];
            cycle_pos[v] = cycle_pos[nxt];
            cycle_len[v] = cycle_len[nxt];
            dist_to_cycle[v] = dist_to_cycle[nxt] + 1;
            cycle_entry[v] = cycle_entry[nxt];
        }
    }

    int jump(int v, long long k) const {
        for (int i = 0; i < LOG; ++i) {
            if ((k >> i) & 1) v = up[i][v];
        }
        return v;
    }

    bool in_cycle(int v) const {
        return dist_to_cycle[v] == 0;
    }

    int cycle_id(int v) const {
        return comp_id[v];
    }

    int cycle_size(int v) const {
        return cycle_len[v];
    }

    int steps_to_cycle(int v) const {
        return dist_to_cycle[v];
    }

    int cycle_vertex(int v) const {
        return cycle_entry[v];
    }

    int cycle_index(int v) const {
        return cycle_pos[v];
    }

    const vector<int> &cycle(int id) const {
        return cycles[id];
    }
};

/**
 * @brief Functional Graph
 */

Back to top page