Топологическая сортировка, но с определенной группировкой

Question

Похоже, это обычная проблема с расписанием, но я не вижу решения или даже как назвать проблему. Это похоже на топологическую сортировку, но по-другому ....

Учитывая некоторые зависимости, скажем

родовое слово

Для топологической сортировки может быть несколько решений:

родовое слово

оба решения.

Мне нужен алгоритм, который вернет это:

родовое слово

То есть выполните A, затем все B и C, затем вы можете сделать D. Все неоднозначности или безразличия сгруппированы.

Я думаю, что такие алгоритмы, как Топологическая сортировка с группировкой , не будут правильно обрабатывать случаи. вроде следующего.

родовое слово

Для этого алгоритм должен вернуть

родовое слово

Это

родовое слово

должен вернуться

родовое слово

Пока это

родовое слово

должен вернуться

родовое слово

И это

родовое слово

должен вернуться

родовое слово

Есть название и обычное решение этой проблемы? (И правильно ли справляются с этим алгоритмы, опубликованные на Топологической сортировке с группировкой ?)

Отредактируйте, чтобы ответить на запросы о дополнительных примерах:

родовое слово

должен вернуться

родовое слово

И

родовое слово

должен вернуться

родовое слово

И

родовое слово

должен вернуться

родовое слово

Answer 1

Пусть G - транзитивное замыкание графа.Пусть G '- неориентированный граф, полученный в результате удаления ориентации из G и взятия дополнения.Связанные компоненты G '- это наборы, которые вы ищете.