Можно ли разбить ориентированный граф на две группы так, чтобы узлы не соединялись друг с другом в группах?

Question

Я ищу алгоритм, который проверяет, что для данного ориентированного графа его узлы можно разделить на две группы, так что узлы не соединяются друг с другом в пределах своей группы

Например

UPD

Мне нужно проверить двудольные графы, вот и все

Answer 1

Граф, который вы описываете, называется Двудольный граф .

Это является способ проверить, является ли данный граф двудольным или нет.