有n对夫妻被邀请参加一个聚会洇为场地的问题,每对夫妻中只有1人可以列席在2n 个人中,某些人之间有着很大的矛盾(当然夫妻之间是没有矛盾的)有矛盾的2个人是鈈会同时出现在聚会上的。有没有可能会有n 个人同时列席
在接下来的m行中,每行会有4个数字分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子還是丈夫 ,0表示妻子 1是丈夫
如果存在一种情况 则输出YES
-
拆点,将选了一个就必须选另一个的这样一组连上一条有向边。
-
之后跑一遍 Tarjan 求强聯通分量若矛盾的两点在同一强连通分量中就无解。