Обход в глубину

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

Немного его модифицируем, а именно будем сохранять для каждой вершины, в какой момент мы в неё вошли и в какой вышли — соответствующие массивы будем называть \(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\)-ам, то индексы любого поддерева всегда будут каким-то промежутком в этой нумерации.

Эти свойства часто бывают полезными в задачах на деревья.