Пусть G = (V, E) - сильно связный ориентированный граф. Начните с графика G '= (V, {}). Нам дан список L ребер в E такой, что каждое ребро в L, которое мы добавляем к G '(по порядку), соединяет две сильно связные компоненты. Какой быстрый алгоритм позволяет отслеживать сильно связанные компоненты G, когда мы добавляем по одному ребру за раз? Использование алгоритма Косараю или Тарьяна на каждом шаге занимает время O (| E | (| V | + | E |)), которое, я думаю, можно улучшить.