Day 027-Q2 — Functional Graph（ρ形状・周期検出・到達頂点数え上げ）

2026-05-10 赤色 Master / Phase 8+ ★★★★★★★★★ Functional Graph

問題

$N$ 頂点の有向グラフがあり、各頂点 $i$ からちょうど1本の辺 $i \to f(i)$ が出ている（Functional Graph）。$Q$ 個のクエリ $(v, k)$ について、頂点 $v$ から辺を $k$ 回辿った頂点番号を答えよ。

入力形式

N Q
f(1) f(2) ... f(N)
v_1 k_1
...
v_Q k_Q

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq f(i) \leq N$
$0 \leq k \leq 10^{18}$

入出力例

入力例 1

6 3
2 3 4 2 6 5
1 0
1 5
3 100

出力例 1

1
3
4

グラフ: 1→2→3→4→2（サイクル長3）、5→6→5（サイクル長2）

ヒント (段階的開示)

ヒント1: 方向性
Functional Graph では各連結成分が「ρ（ロー）形」: 1つのサイクルと、そこに接続する木（尾）で構成される。頂点 $v$ から $k$ ステップ先を求めるには、まず尾の部分をスキップし、サイクルに入ったら剰余計算をする。
ヒント2: アプローチ
  1. 属するサイクルのID・サイクル長・サイクル内位置
  2. サイクルまでの距離（尾の長さ）
  3. 祖先ジャンプテーブル（Binary Lifting）で $2^j$ ステップ先の頂点
クエリ処理: $k \leq d$ なら Binary Lifting、$k > d$ ならサイクル剰余。
ヒント3: 誘導 
LOG = 62
anc = [[0] * (N+1) for _ in range(LOG)]
anc[0] = [0] + f_list
for j in range(1, LOG):
    for v in range(1, N+1):
        anc[j][v] = anc[j-1][anc[j-1][v]]

def jump(v, k):
    for j in range(LOG-1, -1, -1):
        if k >= (1 << j):
            v = anc[j][v]
            k -= (1 << j)
    return v

模範解答 (Python)

import sys
from collections import deque
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    f = [0] + list(map(int, input().split()))  # 1-indexed

    LOG = 62
    anc = [[0] * (N + 1) for _ in range(LOG)]
    anc[0] = f[:]
    anc[0][0] = 0
    for j in range(1, LOG):
        for v in range(1, N + 1):
            anc[j][v] = anc[j-1][anc[j-1][v]]

    def jump(v, k):
        for j in range(LOG - 1, -1, -1):
            if k >> j & 1:
                v = anc[j][v]
        return v

    color = [0] * (N + 1)
    in_cycle = [False] * (N + 1)
    cycle_len = [0] * (N + 1)
    dist_to_cycle = [-1] * (N + 1)

    for start in range(1, N + 1):
        if color[start] == 2:
            continue
        path = []
        visited_in_path = {}
        v = start
        while color[v] == 0:
            color[v] = 1
            visited_in_path[v] = len(path)
            path.append(v)
            v = f[v]

        if color[v] == 1 and v in visited_in_path:
            cycle_start_idx = visited_in_path[v]
            cl = len(path) - cycle_start_idx
            for i in range(cycle_start_idx, len(path)):
                u = path[i]
                in_cycle[u] = True
                cycle_len[u] = cl
                dist_to_cycle[u] = 0
                color[u] = 2
            for i in range(cycle_start_idx - 1, -1, -1):
                u = path[i]
                dist_to_cycle[u] = dist_to_cycle[f[u]] + 1
                cycle_len[u] = cycle_len[f[u]]
                color[u] = 2
        else:
            for i in range(len(path) - 1, -1, -1):
                u = path[i]
                if color[u] == 2:
                    break
                dist_to_cycle[u] = dist_to_cycle[f[u]] + 1
                cycle_len[u] = cycle_len[f[u]]
                color[u] = 2

    out = []
    for _ in range(Q):
        v, k = map(int, input().split())
        d = dist_to_cycle[v]
        if k <= d:
            out.append(jump(v, k))
        else:
            v2 = jump(v, d)
            rem = (k - d) % cycle_len[v2]
            out.append(jump(v2, rem))

    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

1Functional Graph の構造
各頂点の出次数が1のグラフは必ず「ρ形」になる。尾（Rho の棒）はサイクルに向かって流れる木の部分、サイクル（Rho の輪）は各連結成分に必ず1つ存在。
2Binary Lifting の構築
$O(N \log(\max k))$ の前処理で、$2^j$ ステップ先の頂点を記録。anc[j][v] = anc[j-1][anc[j-1][v]]。
3サイクル検出と距離計算
各頂点を辿りながらパスを記録し、訪問済み頂点に再到達した時点でサイクルを特定。$O(N)$ で全頂点の dist_to_cycle と cycle_len を確定。
4クエリ処理
$k \leq d$: サイクルに届かない → Binary Lifting で $k$ ステップ先。$k > d$: サイクル入口に移動し残り (k - d) % cycle_len ステップ。全体 $O((N+Q) \log k)$。

よくあるミス

ミス原因正しい書き方
Binary Lifting で $k$ の bit 処理が逆順MSB から処理しないとオーバーシュートfor j in range(LOG-1, -1, -1)
サイクル検出の再帰が深くて TLEN≤2×10^5 では再帰スタックが問題反復実装にする
dist_to_cycle が -1 のまま確定済み頂点を踏んだ時の分岐処理漏れcolor[v]==2 の場合を正しく処理
剰余計算を $k \bmod \text{cycle\_len}$ だけにするサイクル入口までの距離を引き忘れ(k - d) % cycle_len

次のステップ

  • 発展問題: 同 Functional Graph で、頂点 $v$ から $k$ ステップ以内に到達できる異なる頂点の数を求めよ（$k \leq 10^{18}$）

自己評価

自分の回答

気づき・メモ