题目链接：https://vjudge.net/problem/POJ-1417 题目大意：世界上有两种人，一种是好人，他们说的每句话都是实话；另一种人是坏人，他们说的每句话都是假话。你可以问他们别人（包括他自己）是不是好人，他们会给你"yes"或者"no"的回答。现在给出n次提问，并且告诉你了好人和坏人人数，问你是不是有且只有一种合法的情况。如果是，就顺序输出好人；如果不是就输出"no"

POJ连炸多日…… 题目 岛上有两种人，一种只说假话，一种只说真话。给出两种人的数量和一些你问他们的问题（问A，B是不是说真话），问是否能确定每个人到底是说真话还是说假话。 题解 1.发现a,b相同会回答yes 否则回答no 2.套用并查集模板 画图 设边权：相同为0，不同为1 猜\(fav[fa1]=fav[a] \) xor \( fav[b] \;\) xor \( d\)，枚举各种情况

大过年的也是被这一题搞得崩溃 然后也没网络没法搜题解 所以当时也是挺崩溃的 不过貌似卡住的地方似乎也不是并查集的范畴 这一题也是挺好联系并查集的 告诉n句话并指明有 x个巫师 y个恶魔 给出xi yi YES/NO 来代表 xi说yi是否是巫师 最后如果能肯定哪些是巫师 则输出这些人并加end作为输出结束 否则输出no 可以根据示例输入列个表 1Y2Y 1N2N

有一点小转化的题，在设计dp状态时还是有点费脑筋的。 地址。 依题意，首先可以知道肯定要扩展域的并查集（明摆着的嘛）。一个"好人"域，一个"坏人"域，每句话分两种情况考虑连边。假设是yes，同域连边，否则异域连边（经典模型嘛）。然后就是要考虑如何验证是否有$x$个好人$y$个坏人的唯一解存在。这取决于联通块。 可以参考我瞎画的图，上面点1~N,下面点N+1~2N。 由于并查集合并时操作的对称

传送门 每个点拆成两个,表示好人或坏人 我们合并集合后,发现存在几组对立的集合 也就是说这个集合和与它对立的集合只能选一个 我们用rt1[i] , rt2[i] 表示第i个集合 和 与第i个集合对立的集合 cnt1,cnt2表示该集合好人的个数 用f[i][j]表示到第i个集合,好人为j的方案数 同时记录from[i][j] 表示f[i][j]选的是第i组集合的哪一个集合

True Liars POJ - 1417   点击打开链接 这题时kuangbin大大的并查集专题里面的，解法也是kuangbin大大的解法，但是加上了一点我的理解   题意：    给你p1个好人和p2个坏人，编号为1-p1+p2，然后给你n中操作                    x1 x2 no：x1说x2不是好人                     x1 x2 ye