Day 079-Q1 — Functional Graph: Cycle Detection + Binary Lifting（ρ形状・周期クエリ）

問題

$N$ 頂点の機能グラフ（Functional Graph）が与えられる。 各頂点 $i$（$1 \le i \le N$）にはちょうど 1 本の有向辺が出ており、その先は $f_i$ である。 つまり、各頂点から辺を 1 回たどると頂点 $f_i$ に移動する。

$Q$ 個のクエリが与えられる。各クエリ $(v, K)$ に対して、 「頂点 $v$ から $K$ 回移動したとき、最終的にいる頂点番号」を答えよ。

機能グラフの各弱連結成分はちょうど 1 つのサイクル（自己ループも含む）を持つ（$\rho$ 形状）。 $K$ は最大 $10^{18}$ と非常に大きいため、シミュレーションでは絶対に間に合わない。

入力形式

N Q
f_1 f_2 ... f_N
v_1 K_1
v_2 K_2
...
v_Q K_Q

入出力例

6 3
2 3 4 2 6 5
1 1
1 3
1 7

2
4
2

グラフ: $1\to2\to3\to4\to2$（サイクル $2\to3\to4\to2$、長さ3）、$5\to6\to5$（サイクル長2）。 クエリ $(1,7)$: テール1ステップで頂点2、残り $6\bmod3=0$ ステップ → 頂点2。

5 4
2 3 1 5 4
1 0
1 3
4 1
4 10

1
1
5
4

グラフ: $1\to2\to3\to1$（サイクル長3）、$4\to5\to4$（サイクル長2）。 クエリ $(4,10)$: $10\bmod2=0$ → 頂点4。

概念図: Functional Graph の ρ 形状と Binary Lifting

緑色の頂点 {2,3,4} がサイクル（長さ3）。頂点1はテール（dist_to_cycle=1）。 青色の {5,6} は別連結成分のサイクル（長さ2）。 下部パネルに Binary Lifting テーブルの漸化式とクエリ処理のビット展開を示す。

ヒント

# Binary Lifting テーブル構築
LOG = 62
up = [nxt[:]]        # up[0][v] = nxt[v]（1回移動、1-indexed）
for k in range(1, LOG):
    prev = up[k - 1]
    cur = [0] * (N + 1)
    for v in range(1, N + 1):
        cur[v] = prev[prev[v]]  # 2^k = 2^(k-1) + 2^(k-1)
    up.append(cur)

def go(v, K):
    """頂点 v から K 回移動した先を O(log K) で返す"""
    for bit in range(LOG):
        if (K >> bit) & 1:   # K の bit 番目が立っている
            v = up[bit][v]   # 2^bit ステップ進む
    return v

# クエリ処理
for _ in range(Q):
    v, K = map(int, input().split())
    print(go(v, K))

模範解答

方法A: Binary Lifting のみ（シンプル・推奨）

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx + 1])
    idx += 2

    # nxt[v] = 頂点 v の次の頂点（1-indexed）
    nxt = [0] * (N + 1)
    for v in range(1, N + 1):
        nxt[v] = int(data[idx])
        idx += 1

    # ─── Binary Lifting テーブル構築 O(N * LOG) ─────────────────
    # up[k][v] = 頂点 v から 2^k 回移動した先の頂点
    # K <= 10^18 < 2^62 なので LOG = 62 で全ビットをカバー
    LOG = 62
    up = [list(nxt)]   # up[0]: index 0 は番兵（使わない）
    for k in range(1, LOG):
        prev = up[k - 1]
        cur = [0] * (N + 1)
        for v in range(1, N + 1):
            cur[v] = prev[prev[v]]
        up.append(cur)

    # ─── クエリ処理 O(Q * LOG) ──────────────────────────────────
    # K をビット展開: K = sum(2^bit for bit where bit is set)
    # 各ビットに対応する 2^bit ステップを順番に適用
    out = []
    for _ in range(Q):
        v, K = int(data[idx]), int(data[idx + 1])
        idx += 2
        for bit in range(LOG):
            if (K >> bit) & 1:
                v = up[bit][v]
        out.append(v)

    sys.stdout.write('\n'.join(map(str, out)) + '\n')

solve()

方法B: サイクル検出 + mod 最適化（発展・完全版）

import sys
from collections import deque

def solve_cycle():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx + 1])
    idx += 2

    nxt = [0] * (N + 1)
    for v in range(1, N + 1):
        nxt[v] = int(data[idx])
        idx += 1

    # ─── サイクル頂点を in-degree BFS で特定 ────────────────────
    indeg = [0] * (N + 1)
    for v in range(1, N + 1):
        indeg[nxt[v]] += 1

    q = deque(v for v in range(1, N + 1) if indeg[v] == 0)
    on_cycle = [True] * (N + 1)
    on_cycle[0] = False
    while q:
        v = q.popleft()
        on_cycle[v] = False
        w = nxt[v]
        indeg[w] -= 1
        if indeg[w] == 0:
            q.append(w)

    # ─── 各サイクルの長さを計算 ─────────────────────────────────
    cycle_len = [0] * (N + 1)
    visited_c = [False] * (N + 1)
    for start in range(1, N + 1):
        if on_cycle[start] and not visited_c[start]:
            v, length = start, 0
            while True:
                visited_c[v] = True
                length += 1
                v = nxt[v]
                if v == start:
                    break
            v = start
            while True:
                cycle_len[v] = length
                v = nxt[v]
                if v == start:
                    break

    # ─── テール頂点の dist_to_cycle と cycle_entry をメモ化 ─────
    dist_to_cycle = [-1] * (N + 1)
    cycle_entry = [0] * (N + 1)

    def get_info(start):
        path = []
        v = start
        while not on_cycle[v] and dist_to_cycle[v] < 0:
            path.append(v)
            v = nxt[v]
        if on_cycle[v]:
            base_entry, base_dist = v, 0
        else:
            base_entry = cycle_entry[v]
            base_dist = dist_to_cycle[v]
        for i, u in enumerate(reversed(path)):
            dist_to_cycle[u] = base_dist + i + 1
            cycle_entry[u] = base_entry

    for v in range(1, N + 1):
        if not on_cycle[v]:
            if dist_to_cycle[v] < 0:
                get_info(v)
        else:
            dist_to_cycle[v] = 0
            cycle_entry[v] = v

    # ─── Binary Lifting（テール上のクエリ用） ────────────────────
    LOG = 62
    up = [list(nxt)]
    for k in range(1, LOG):
        prev = up[k - 1]
        cur = [0] * (N + 1)
        for v in range(1, N + 1):
            cur[v] = prev[prev[v]]
        up.append(cur)

    def go_lift(v, k):
        for bit in range(LOG):
            if (k >> bit) & 1:
                v = up[bit][v]
        return v

    out = []
    for _ in range(Q):
        v, K = int(data[idx]), int(data[idx + 1])
        idx += 2
        d = dist_to_cycle[v]
        if K < d:
            result = go_lift(v, K)
        else:
            entry = cycle_entry[v]
            rem = (K - d) % cycle_len[entry]
            result = go_lift(entry, rem)
        out.append(result)

    sys.stdout.write('\n'.join(map(str, out)) + '\n')

solve_cycle()

Step-by-Step 解説

Step 1: 機能グラフの ρ 形状を理解する

機能グラフは各頂点の出次数がちょうど 1 のグラフ。頂点数 $N$、辺数 $N$ なので、 各弱連結成分は必ずちょうど 1 つのサイクルを含む（鳩の巣原理）。

テール:  1 → 2 ─┐
                 ↓
サイクル: ┌── 2 ← 4
          └→ 3 ──┘    （cycle_len = 3）

• サイクル頂点: グラフの「ループ」部分（dist_to_cycle = 0）
• テール頂点: サイクルに繋がるが自身はサイクル外（dist_to_cycle > 0）

$K$ 回移動の動作: テール頂点 $v$ に対して、 $K < d_v$ ならテール内で完結、 $K \ge d_v$ ならサイクル入口から $(K - d_v) \bmod L$ ステップ。

Step 2: Binary Lifting テーブルの構築 $O(N \log K)$

倍加法の核心: $2^k$ ステップ先を前計算し、任意の $K$ を $O(\log K)$ で処理する。

$K \le 10^{18} < 2^{60}$ だが余裕を持って LOG = 62 とする。 空間: $O(N \times 62) \approx 1.24 \times 10^7$ 整数。

Step 3: クエリを $O(\log K)$ で処理する

$K$ を 2 進数で展開し、立っているビットに対応する up[bit] を順次適用する。

def go(v, K):
    for bit in range(LOG):
        if (K >> bit) & 1:   # K の bit 番目が立っている
            v = up[bit][v]   # 2^bit ステップ進む
    return v

例: $K = 7 = 2^0 + 2^1 + 2^2$ → bit=0,1,2 で計 $1+2+4=7$ ステップ進む。

Step 4: サイクル頂点の特定（位相的ソート逆用）

in-degree 0 の頂点からキュー BFS でテール頂点を順次除去。 最終的に残った頂点集合 = サイクル頂点。

1. 全頂点の in-degree を計算
2. in-degree 0 の頂点をキューに積む（テール確定）
3. 取り出した頂点の次の頂点の in-degree を -1。0 になればキューに追加
4. キューが空になったとき、残りの頂点 = サイクル上

Step 5: 計算量分析

$N = Q = 2\times10^5$, LOG = 62 で合計 $\approx 2.5\times10^7$ 演算。PyPy で十分高速。

よくあるミス

次のステップ

• 発展問題1: K 回適用の逆関数（頂点 v の K ステップ前にいた可能性のある頂点を全列挙）。テール上の頂点の逆辿りは逆グラフの BFS/DFS で列挙可能だが、サイクル上は複数の候補がある。
• 発展問題2: 辺に重みが付いた機能グラフで、K 回移動したときの重みの総和を求めよ。Binary Lifting テーブルを (next_vertex, weight_sum) のペアに拡張する。
• 発展問題3: 機能グラフ上で「頂点 u と頂点 v が最初に合流する頂点と必要ステップ数」を求めよ（合流点問題・ρ 形状 LCA）。
• AtCoder 関連問題: ABC 167 D「Teleporter」（機能グラフ + Binary Lifting の典型問題）、ABC 258 E「Packing Potions」。

自己評価