Поиск в глубину - Алгоритмика

Поиском в глубину (англ. 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$ .

Как их заполнить: заведем таймер, отвечающий за «время» на текущем состоянии обхода, и будем инкрементировать его каждый раз, когда заходим в новую вершину:

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$ -ам, то индексы любого поддерева всегда будут каким-то промежутком в этой нумерации.

Как мы дальше увидим, эти свойства очень полезны в других обходах и самых разных задачах на деревья.