Как быстро свернуть узлы в графе, где каждый узел должен быть принят/отклонен? ⇐ C++

[Anonymous]

Мне нужно представить отношения между людьми в виде графика, чтобы создать список людей, которых следует пригласить на вечеринку. Каждая связь задается в виде кортежа (A, B, cond), где A и B — разные люди, а cond — одно из следующих:

• 0: либо A, B, либо оба должны быть приглашены;
• 1: если A исключен, B должен быть исключен;
• 2: если B исключен, A должен быть исключен;< /li>
  3: либо A, B, либо оба должны быть исключены;

Обратите внимание, что любой список приглашенных людей принимается при условии, что все отношения остаются действительными.
Я попытался смоделировать данные, используя два генеральных директора (один по приглашениям, один по исключениям), отметив, что случаи 1 и 2 налагают одни и те же условия, но поменялись местами. Еще одно замечание заключается в том, что в случаях 1 и 2, если последний приглашен, это приводит к приглашению и первого.
Чтобы получить действительный ответ, я запустил DFS через DG. , сворачивая узлы, которые не были приняты/отклонены. Однако этот метод требует слишком много времени для больших объемов данных. Есть ли лучший подход к таким проблемам, как эта? Я пробовал искать, но ничего не появляется.

Подробнее здесь: https://stackoverflow.com/questions/785 ... epted-reje