Поиском в глубину (англ. 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$-ам, то индексы любого поддерева всегда будут каким-то промежутком в этой нумерации.
Как мы дальше увидим, эти свойства очень полезны в других обходах и самых разных задачах на деревья.