lca아이디어1 후속 노드 그래프 (Successor graph), 희소테이블 모든 정점에 대해 인접한 정점이 단 하나인 그래프로, 함수형 그래프(functional graph)라고도 부른다. succ(x)의 형태로 후속 노드 그래프의 모든 간선을 표현할 수 있기 때문. 후속 노드 그래프는 하나 이상의 컴포넌트로 구성돼 있고, 각각의 컴포넌트는 사이클 '하나'와 그 사이클로 가는 경로로 구성되어 있다. (그래프의 끝에 사이클이 단 하나 달린 형태) 트리구조와 유사하다.(트리에서 루트노드가 자식중 어딘가 가리키고 있다면 후속노드 그래프가 된다. -- 그건 더이상 트리가 아님) 희소테이블 p[u][k]에 이 구조를 담아 푸는 문제가 대부분 - 정점 u에서 k번 이동한 후의 정점을 log시간에 구하기 기본문제 : https://cses.fi/problemset/task/1750 널리쓰이.. 2020. 1. 29. 이전 1 다음