关于真假话类问题的最值问题

Question

拿一个情景距离
假设有n个人，分为两类，一类说真话，一类说假话。
然后输入一堆信息表示谁指认另一个人会说真话还是假话，一个人可能会多次指认。
然后要求可能的情况中最多的会说真话的人数。
对于这种类型的算法题有什么思路吗

Answer 1

例子：a b c d e f

• 指认x说真话的，一类人，指认x说假话的一类人，按这个规则，可以找到一个大致的网络（可传递），a说b是说真话，c说b是说真话（说明a和c同真假），a说d说假话，e说d说假话（说明a和e同真假）
• 可推出a/c/e三个人同真假，又a说b是真，所以a和b又同真假，可推a指认b真，两者同真假;a说d是假，所以a和d的真假性相反
• 由此可知：a/b/c/e同真假，d和他们相反,f未知，所以f为真时量最多

我的思路是并查集建立连接，同时携带和根节点的异同信息；子节点通过getRoot()找到根节点，根节点和同真假的建立一批映射，不同真假的建立一批映射，然后在这个基础上dfs，找出最多真话的

如果没有学过并查集，直接用dfs查也可以，就是时间久一点，那就思路简单点，a说b是真，则a和b同真假，a说b为假，则a和b不同真假