目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
| 1594D - The Number of Imposters |
二、解题报告
1、思路分析
并查集，扩展域并查集，带边权并查集详解，OJ练习，详细代码_拓展域并查集-CSDN博客
一眼类似于扩展域并查集可解决的问题
这个题就是在玩太空狼人杀
好人不说谎，坏人不吐真
A说B是坏人，那么A、B一定是不同阵营的
A说B是好人，那么A、B一定是同一阵营的
这是简单的数理逻辑
那么我们可以根据关系建图，从而二染色
我们并不关注哪个颜色是好人，我们对每个连通块选取颜色最多的那个作为坏人的数目即可
具体实现：
相同阵营，说明颜色相同，边权为0，传颜色传c ^ 0
不同阵营，说明颜色不同，边权为1，传颜色传c ^ 1
另：py递归爆内存，用栈来递归
2、复杂度
时间复杂度： O(N + M)空间复杂度：O(N + M)
3、代码详解
import sys
from math import infinput = lambda: sys.stdin.readline().strip()
MII = lambda: map(int, input().split())
LMI = lambda: list(map(int, input().split()))
LI = lambda: list(input())
II = lambda: int(input())
fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
P = 10**9 + 7def solve():n, m = MII()g = [[] for _ in range(n)]for _ in range(m):a, b, s = input().split()a, b = map(int, [a, b])a -= 1b -= 1w = 1 if s[0] == 'i' else 0g[a].append([b, w])g[b].append([a, w])color = [-1] * ncnt = [0, 0]def dfs(x: int, y: int) -> bool:stk = [x]color[x] = ycnt[y] += 1while stk:u = stk[-1]stk.pop()c = color[u]for v, w in g[u]:if ~color[v] and color[v] != c ^ w:return Falseelif color[v] == -1:stk.append(v)color[v] = c ^ wcnt[c ^ w] += 1return Trueres = 0for i in range(n):if ~color[i]:continuecnt = [0, 0]if not dfs(i, 0):print(-1)returnres += fmax(cnt[0], cnt[1])print(res)if __name__ == "__main__":T = 1T = II()for _ in range(T):solve()
