Компоненты связности

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

Сделаем это с помощью стандартного алгоритма обхода в глубину - dfs.

Алгоритм

Допустим, мы сейчас находимся в вершине $v$ и хотим найти все вершины, которые в одной компоненте с ней.

Сначала пометим $v$ как использованную вершину и запишем её цвет. Затем переберём все вершины $u$, соседние с этой вершиной.

Если в ходе нашего алгоритма мы уже были в $u$, ещё раз заходить в неё мы не будем - в этом нет смысла. Если же мы в ней не были, то запустим алгоритм от неё, пометив её перед этим как использованную.

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

Реализация

Здесь использованы глобальные массивы: used для того, чтобы отмечать посещённые вершины, color для того, чтобы запоминать компоненты и g для реализации списков смежности.

Кроме того, переменная cur_color поддерживает, в какой цвет мы сейчас красим, и по совместительству равна количеству компонент.

def dfs(v):
    used[v] = True
    color[v] = cur_color
    for u in g[v]:
        if not used[u]:
            dfs(u)


for v in range(n):
    if not used[v]:
        dfs(v)
        cur_color += 1

Асимптотика

На первый взгляд кажется, что даже один запуск функции dfs будет очень долгим. На самом деле это не так: каждый запуск dfs будет работать за $O(n + m)$, где $n$ - количество вершин в компоненте, а $m$ - количество рёбер в ней. Это верно, потому что каждое ребро будет рассмотрено никак не более 2 раз.

Становится ясно, что тогда и весь алгоритм работает за $O(n + m)$.

Проверка на двудольность

Двудольным называется граф, вершины которого можно разбить на 2 множества так, что все рёбра ведут из одной доли в другую.

Будем снова красить граф, но в этот раз - в 2 цвета, после каждого перехода меняя цвет. Если в какой-то момент вершина, смежная с текущей, уже окажется покрашена в неправильный цвет, то есть в цвет текущей вершины - граф не двудольный. Асимптотика - такая же, как у dfs, то есть $O(n + m)$.

Поиск цикла

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

Этот же подход используют, когда на вход заведомо дано дерево, поскольку он позволяет избавиться от массива used и таким образом сохранить много памяти.

Реализация

def dfs(v, p):
    used[v] = True
    res = False
    for u in g[v]:
        if not used[u]:
            res = res or dfs(u)
        elif used[u] and u != p:
            res = True
    return res
    
    
print(dfs(0, 0))