깊이 우선 탐색 - 알고리즘카

깊이 우선 탐색(영어: depth-first search, DFS) 또는 오일러 투어는 루트 노드에서 시작하여(그래프의 경우 임의의 정점을 선택할 수 있습니다) 각 정점을 정확히 한 번씩 방문하면서 그래프 전체를 재귀적으로 순회하는, 루트 있는 트리 또는 그래프를 순회하는 재귀 알고리즘입니다.

const int maxn = 1e5;
bool used[maxn]; // тут будем отмечать посещенные вершины

void dfs(int v) {
    used[v] = true;
    for (int u : g[v])
        if (!used[u])
            dfs(u);
}

이를 약간 수정하겠습니다. 구체적으로는 각 정점마다 그 정점에 언제 들어갔고 언제 나왔는지를 저장하겠습니다. 이에 해당하는 배열을 각각 $tin$과 $tout$이라고 부르겠습니다.

이 배열들을 채우는 방법은 다음과 같습니다. 현재 탐색 상태에서의 ‘시간’을 나타내는 타이머를 하나 두고, 새로운 정점에 들어갈 때마다 이 타이머를 1씩 증가시킵니다.

int tin[maxn], tout[maxn];
int t = 0; // таймер

void dfs(int v) {
    tin[v] = t++;
    for (int u : g[v])
        if (!used[u])
            dfs(u);
    tout[v] = t; // иногда счетчик тут тоже увеличивают
}

이 배열들에는 유용한 성질이 많습니다:

정점 $u$가 $v$의 조상인 것은 $\iff tin_v \in [tin_u, tout_u)$입니다. 이 검사는 상수 시간에 할 수 있습니다.
두 반구간 $[tin_v, tout_v)$와 $[tin_u, tout_u)$는 서로 겹치지 않거나, 한쪽이 다른 쪽에 포함됩니다.
배열 $tin$에는 0부터 $(n - 1)$까지의 모든 수가 들어 있으며, 각 정점은 서로 다른 번호를 가집니다.
정점 $v$의 서브트리 크기(정점 자신 포함)는 $(tout_v - tin_v)$입니다.
정점에 $tin$ 값에 대응하는 번호를 매기면, 임의의 서브트리에 속한 정점들의 인덱스는 이 번호 체계에서 항상 하나의 구간을 이룹니다.

앞으로 보게 되겠지만, 이러한 성질은 다른 순회와 트리에 관한 매우 다양한 문제에서 아주 유용합니다.