HDU3062Party
2520+
作者：crxis 发布：2020-12-23 分类：强连通
题目大意：n对夫妻参加聚会，人数有限只能派一人做代表，这2n人中，有些存在矛盾，不能同时出席，请问能否做得没对夫妻都派出1人参加聚会且不发生冲突。
Problem Description
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？
Input
n： 表示有n对夫妻被邀请 (n<= 1000)
m： 表示有m 对矛盾关系 ( m < (n – 1) * (n -1))
在接下来的m行中，每行会有4个数字，分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子还是丈夫 ，0表示妻子 ，1是丈夫
夫妻编号从 0 到 n -1
m： 表示有m 对矛盾关系 ( m < (n – 1) * (n -1))
在接下来的m行中，每行会有4个数字，分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子还是丈夫 ，0表示妻子 ，1是丈夫
夫妻编号从 0 到 n -1
Output
如果存在一种情况 则输出YES 否则输出 NO
Sample Input
2 1 0 1 1 1
Sample Output
YES
解题思路
只需要判断是否可行，缩点后判断一对夫妻是否在同一个集合即可。
存储：妻子编号1到n，丈夫编号n+1到n+n。x和y有冲突，那么x只能和y+n搭配，y只能和x+n搭配；x和y+n有冲突，那么x只能和y搭配，y+n只能和x+n搭配。什么时候加n？异或关系！
建图后，缩点，如果同一对夫妻在一个集合，要么都去，要么都不去，不可能做得n个人n对夫妻都包含。
程序实现
