Поиск в глубину

Поиском в глубину (англ. depth-first search, DFS) называется рекурсивный алгоритм обхода дерева или графа, начинающий в корневой вершине (в случае графа её может быть выбрана произвольная вершина) Он рекурсивно обходит весь граф, и посещает каждую вершину ровно один раз. Посещенные вершины при этом отмечаются в массиве used.

Давайте его немного модифицируем, а именно, давайте сохраним в какой-нибудь массив, в каком порядке мы посещали вершины. Есть два способа это сделать - посчитать время входа DFS-а в каждую вершину и время выхода.

Давайте назовем массивы tin и tout, где tin — время входа, а tout — время выхода из вершины.

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

int tin[maxn], tout[maxn];
int timer = 0;

void dfs(int v) {
    tin[v] = timer++;
    for (int i = 0; i < g[v].size(); ++i) {
        if (!used[g[v][i]]) {
            dfs(g[v][i]);
        }
    }
    tout[v] = timer++;
}

Время входа или выхода пригождается во многих алгоритмах, например, при поиске мостов, поиске точек сочленения.