Описание задачи
Задача: Обнаружение сильных связных компонент (SCC)
Необходимо определить сильные связные компоненты в заданном ориентированном графе. Сильная связная компонента – это подграф, где можно найти путь между любыми двумя вершинами внутри этого подграфа.
Входные данные:
n: Целое число, представляющее количество вершин в графе (от 0 до n-1).edges: Список кортежей, где каждый кортеж(u, v)представляет ребро ориентированного графа от вершиныuк вершинеv.
Выходные данные:
comp: Список целых чисел длинойn, гдеcomp[i]указывает на идентификатор сильной связной компоненты, в которой находится вершинаi.c: Целое число, представляющее количество сильных связных компонент в графе.
Режим обучения Готово
Объяснение решения уже подготовлено. Нажмите кнопку, чтобы посмотреть.
Ваше решение
Подсказка (готовое решение)
def kosaraju(n, edges):