← Назад к списку задач

kosaraju scc

Общее Уровень 2

Описание задачи

Задача: Обнаружение сильных связных компонент (SCC)

Необходимо определить сильные связные компоненты в заданном ориентированном графе. Сильная связная компонента – это подграф, где можно найти путь между любыми двумя вершинами внутри этого подграфа.

Входные данные:

  • n: Целое число, представляющее количество вершин в графе (от 0 до n-1).
  • edges: Список кортежей, где каждый кортеж (u, v) представляет ребро ориентированного графа от вершины u к вершине v.

Выходные данные:

  • comp: Список целых чисел длиной n, где comp[i] указывает на идентификатор сильной связной компоненты, в которой находится вершина i.
  • c: Целое число, представляющее количество сильных связных компонент в графе.

Режим обучения Готово

Объяснение решения уже подготовлено. Нажмите кнопку, чтобы посмотреть.

Ваше решение

Подсказка (готовое решение)

def kosaraju(n, edges):