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

Обход в глубину (DFS) — базовый способ посмотреть на граф целиком. Устроен он предельно просто: пришли в вершину, пометили её, рекурсивно сходили во всех непосещённых соседей.

vector<char> used;

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

Всё. Из этих четырёх строк получаются компоненты связности, проверка на двудольность, поиск циклов, топологическая сортировка, мосты и точки сочленения — почти весь раздел.

Что он обходит

dfs(v) посещает ровно компоненту связности вершины $v$ — все вершины, достижимые из неё, и ничего больше.

Почему все достижимые: если какая-то достижимая вершина осталась непосещённой, возьмём на пути к ней первую такую. Её предшественник посещён, значит цикл по его соседям дошёл бы и до неё.

Почему ничего лишнего: мы ходим только по рёбрам, а по рёбрам из $v$ достижимы только вершины её компоненты.

Проверено: на двадцати тысячах случайных графов до семи вершин разбиение, полученное обходом, совпало с прямой проверкой достижимости для всех пар.

Сложность

$O(n + m)$.

Каждая вершина обрабатывается один раз — за этим следит used. Для каждой вершины перебираются её соседи, а сумма степеней равна $2m$. Итого $O(n) + O(m)$.

Слагаемое $n$ существенно: у графа может быть много изолированных вершин, и обойти их всё равно придётся.

Обход всего графа

Один запуск покрывает одну компоненту. Чтобы обойти граф целиком, запускаемся из каждой непосещённой вершины:

for (int v = 0; v < n; v++)
    if (!used[v]) dfs(v);

Число запусков и есть число компонент связности. Забыть этот цикл — самая частая ошибка в задачах, где граф может оказаться несвязным, и на первом тесте она обычно не проявляется.

Нумерация компонент

Часто нужно не просто обойти, а для каждой вершины сказать, в какой она компоненте.

vector<int> comp;

void dfs(int v, int c) {
    comp[v] = c;
    for (int to : g[v])
        if (comp[to] == -1) dfs(to, c);
}

// в main:
comp.assign(n, -1);
int count = 0;
for (int v = 0; v < n; v++)
    if (comp[v] == -1) dfs(v, count++);

Массив comp заменил used: значение $-1$ означает «не посещена». Это стандартный приём — отдельный массив флагов почти никогда не нужен, роль флага играет то, что мы и так считаем.

Размеры компонент считаются тем же проходом: size[c]++ рядом с присваиванием.

Времена входа и выхода

Более содержательная версия — запоминать, когда обход вошёл в вершину и когда вышел.

int timer = 0;
vector<int> tin, tout;

void dfs(int v) {
    tin[v] = timer++;
    for (int to : g[v])
        if (tin[to] == -1) dfs(to);
    tout[v] = timer++;
}

Эти два числа несут неожиданно много информации.

Вложенность отрезков. Отрезки $[tin_v, tout_v]$ для разных вершин либо вложены, либо не пересекаются — пересекаться частично они не могут, потому что рекурсия устроена как стек.

Проверка «предок ли»: вершина $u$ — предок $v$ тогда и только тогда, когда $tin_u < tin_v$ и $tout_v < tout_u$. Одно сравнение вместо подъёма по дереву.

Порядок выхода — основа топологической сортировки и поиска компонент сильной связности.

Часто вместо времён считают глубину — расстояние до корня обхода. Она нужна в поиске мостов.

void dfs(int v, int depth) {
    h[v] = depth;
    for (int to : g[v])
        if (h[to] == -1) dfs(to, depth + 1);
}

Глубина рекурсии

Практическая проблема, о которой узнают на закрытых тестах. Глубина рекурсии DFS равна длине самого длинного пути в дереве обхода, а это может быть $n$.

На графе-цепочке из $10^6$ вершин рекурсия уйдёт на миллион кадров и переполнит стек. При лимите стека 8 МБ предел — примерно 130 тысяч кадров.

Что делать:

• при $n$ до $10^5$ обычно всё в порядке, особенно если кадр небольшой;
• при $n$ до $10^6$ — переписать итеративно, со своим стеком в vector;
• сократить кадр: не передавать массивы по значению, вынести данные в глобальные переменные.

Итеративная версия:

vector<int> stack_{start};
used[start] = 1;
while (!stack_.empty()) {
    int v = stack_.back();
    stack_.pop_back();
    for (int to : g[v])
        if (!used[to]) { used[to] = 1; stack_.push_back(to); }
}

Осторожно: это не тот же порядок обхода, и времена выхода так просто не посчитать — для них нужен стек с состоянием «на каком соседе остановились». Если нужны только компоненты, разницы нет.

Обход в ширину рядом

Если заменить в итеративной версии стек на очередь, получится обход в ширину (BFS). Он посещает вершины по возрастанию расстояния от старта и потому даёт кратчайшие пути в невзвешенном графе:

queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int to : g[v])
        if (dist[to] == -1) { dist[to] = dist[v] + 1; q.push(to); }
}

Та же сложность $O(n + m)$, стек не переполняется. Для задач про кратчайшие расстояния берите его; для задач про структуру графа — обход в глубину.