함수 그래프 (Functional Graph)

정의

함수 그래프 (Functional Graph) 는 정점 집합 V 와 함수 f: V → V 로 정의되는 방향 그래프. 각 정점 v 에서 정확히 하나의 간선 v → f(v) 가 나간다. 형태는 여러 사이클 (cycle) + 각 사이클로 들어가는 트리 (tree) 구조.

문제 상황과 동기

PS 에서 “다음 칸으로 이동”, “연결된 정점으로 한 단계” 문제는 out-degree 가 정확히 1 인 그래프. BFS/DFS 로 naive 하게 x 번 진행하면 O(x · N), 구간이 10^9 이상이면 터진다. 핵심 통찰: 경로는 반드시 “tree part → cycle entry → cycle 회전”, 세 구간으로 분해. Floyd’s cycle finding (토끼와 거북) 으로 사이클 길이 + 시작점 O(N) 에 찾고, 나머지는 prefix jump 또는 modular 계산.

자주 등장: BOJ 상태 전이 시뮬레이션, “N 번 이동 후 위치”, “언제 사이클 만나는가”, 해시 충돌 분석, 수열 반복 규칙.

시각화

핵심 아이디어

invariant

정점 v 에서 출발하면 경로는 tree tail → cycle 두 단계.

v → f(v) → f²(v) → ... → entry → [cycle 시작] → entry (다시)

사이클 진입까지 거리 λ (lambda), 사이클 길이 μ (mu).

f^k(v) = {
    tree 안,           k < λ
    cycle 회전,        k ≥ λ,  (k - λ) mod μ 위치
}

Floyd’s cycle finding

토끼 (2배 속도), 거북 (1배 속도):

1. phase 1: 토끼가 사이클 한 바퀴 돌 동안 거북을 따라잡으면 사이클 존재 확정.
2. phase 2: 토끼를 시작점으로, 둘 다 1 step 씩 움직여 만나면 그 점이 entry.
3. phase 3: entry 에서 한 바퀴 돌면 μ.

시간: O(λ + μ), 공간 O(1). 비순환 그래프면 null 이나 범위 밖 도달.

binary lifting (optional)

k 가 큰 경우 f^k(v) 를 O(log k) 에 구하려면:

dp[v][i] = f^(2^i)(v)

전처리 O(N log N), 쿼리 O(log k).

알고리즘

Floyd_cycle(f, start):
    tortoise = start
    hare = start
    # phase 1: 사이클 감지
    loop
        tortoise = f(tortoise)
        hare = f(f(hare))
        if hare == tortoise: break
        if hare null or f(hare) null: return (λ=∞, μ=0)  # 비순환
    # phase 2: entry 찾기
    tortoise = start
    while tortoise ≠ hare:
        tortoise = f(tortoise)
        hare = f(hare)
    entry = tortoise
    # phase 3: μ 측정
    μ = 1
    hare = f(entry)
    while hare ≠ entry:
        hare = f(hare)
        μ++
    # λ 측정
    λ = 0
    p = start
    while p ≠ entry:
        p = f(p)
        λ++
    return (λ, μ, entry)

구현

// Functional graph: Floyd's cycle detection
#include <bits/stdc++.h>
using namespace std;
​
struct Cycle {
  int lambda, mu, entry;
};
​
Cycle floyd(const vector<int>& f, int start) {
  auto step = [&](int x) { return (x >= (int)f.size() || x < 0) ? -1 : f[x]; };
  int t = start, h = start;
  // phase 1
  do {
      t = step(t);
      h = step(step(h));
      if (h < 0 || t < 0) return {-1, 0, -1};
  } while (t != h);
  // phase 2
  int entry = start;
  while (entry != h) { entry = step(entry); h = step(h); }
  // phase 3
  int mu = 1;
  for (int x = step(entry); x != entry; x = step(x)) mu++;
  int lambda = 0;
  for (int x = start; x != entry; x = step(x)) lambda++;
  return {lambda, mu, entry};
}
​
int main() {
  int n, s; cin >> n >> s;
  vector<int> f(n);
  for (auto& v : f) cin >> v;
  auto [lam, mu, ent] = floyd(f, s);
  cout << "lambda=" << lam << " mu=" << mu << " entry=" << ent << "\n";
}

# Functional graph cycle detection
import sys
input = sys.stdin.readline
​
def floyd(f, start):
  def step(x):
      return f[x] if 0 <= x < len(f) else None
  t, h = start, start
  # phase 1
  while True:
      t = step(t)
      h = step(step(h)) if step(h) is not None else None
      if h is None or t is None:
          return None, 0, None
      if t == h:
          break
  # phase 2
  entry = start
  while entry != h:
      entry, h = step(entry), step(h)
  # phase 3
  mu = 1
  x = step(entry)
  while x != entry:
      x = step(x)
      mu += 1
  # lambda
  lam = 0
  x = start
  while x != entry:
      x = step(x)
      lam += 1
  return lam, mu, entry
​
n, s = map(int, input().split())
f = list(map(int, input().split()))
lam, mu, ent = floyd(f, s)
print(f"lambda={lam} mu={mu} entry={ent}")

6 0
1 2 3 4 2 5

lambda=2 mu=3 entry=2

복잡도

변형 / 활용

1. 상태 전이 시뮬레이션

“N 번 이동 후 위치” 문제. k < λ 면 순회, k ≥ λ 면 (k - λ) mod μ.

2. 연결 요소 분석

각 정점에서 Floyd 돌려 entry 찾으면, 같은 entry 를 공유하는 정점끼리 한 “weakly connected component”.

3. 사이클 없는 경우

hare 가 null 이면 무한히 뻗어나가거나 단절. 예: 해시 체인.

4. 다중 출발

여러 시작점이 같은 사이클로 모이는가? entry 기준 그룹.

함정

1. out-degree ≠ 1

일반 그래프라면 functional graph 가 아님. 이 기법 안 먹힘.

2. 범위 체크

f[v] 가 배열 밖이면 비순환. step 함수 null 처리.

3. λ 계산 빠뜨림

phase 1~3 은 μ, entry 만 줌. λ 는 start → entry 거리 따로.

4. k 매우 큰 경우

k > 10^9 면 naive loop 불가. binary lifting 또는 mod μ 쓰기.

BOJ 연습 문제

참고

• 깊이 우선 탐색
• 사이클 탐지
• 이진 점프