후속 노드 그래프 (Successor graph), 희소테이블

모든 정점에 대해 인접한 정점이 단 하나인 그래프로, 함수형 그래프(functional graph)라고도 부른다. succ(x)의 형태로 후속 노드 그래프의 모든 간선을 표현할 수 있기 때문.

 

후속 노드 그래프는 하나 이상의 컴포넌트로 구성돼 있고, 각각의 컴포넌트는 사이클 '하나'와 그 사이클로 가는 경로로 구성되어 있다. (그래프의 끝에 사이클이 단 하나 달린 형태)

 

트리구조와 유사하다.(트리에서 루트노드가 자식중 어딘가 가리키고 있다면 후속노드 그래프가 된다. -- 그건 더이상 트리가 아님)

 

희소테이블 p[u][k]에 이 구조를 담아 푸는 문제가 대부분

 

 

<문제1> - 정점 u에서 k번 이동한 후의 정점을 log시간에 구하기

기본문제 : https://cses.fi/problemset/task/1750

널리쓰이는 lca 알고리즘에 쓰이는 기본 개념이다.

정리해둔 lca : https://suuntree.tistory.com/63?category=805933

 

p[u][k] : 정점 u의 (1<<k)번째 방문정점이라고 하면

p[u][k+1] = p[ p[u][k] ][k] 이다.

 

**p배열을 초기화 하는 코드

//바깥 for문이 k임에 주의. (1<<k)번째 방문점을 먼저 모든 정점에 대해 초기화 한 후 k를 늘려야 함
for (int k = 1; (1 << k) <= 1e9; k++)
	for (int i = 1; i <= n; i++)
		p[i][k] = p[p[i][k - 1]][k - 1];

 

**p배열을 이용해서 정점 u의 k번째 방문 정점을 구하는 코드

ll u, k; cin >> u >> k;

//k보다 작은 2의 거듭제곱 중 가장 큰 값만큼 u를 이동시킨다.
for (int i = 30; i >= 0; i--)
	if (k >= (1 << i)) {
		u = p[u][i];
		k -= (1 << i);
	}

cout << u << '\n';

 

---

<문제2> - distance(u -> v)를 log 시간에 구하기

기본문제 : https://cses.fi/problemset/task/1160

alfredo's code : https://github.com/abeaumont/competitive-programming/blob/master/cses/1160.cc

 

(추가예정.. 트리에서 최단거리 구하는것 비슷하게 진행되는 걸로 보임)

 

<문제3>

https://www.acmicpc.net/problem/14942

희소테이블 연습문제