目录
一、题目
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 inf
input = 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 + 7
def 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 -= 1
b -= 1
w = 1 if s[0] == 'i' else 0
g[a].append([b, w])
g[b].append([a, w])
color = [-1] * n
cnt = [0, 0]
def dfs(x: int, y: int) -> bool:
stk = [x]
color[x] = y
cnt[y] += 1
while stk:
u = stk[-1]
stk.pop()
c = color[u]
for v, w in g[u]:
if ~color[v] and color[v] != c ^ w:
return False
elif color[v] == -1:
stk.append(v)
color[v] = c ^ w
cnt[c ^ w] += 1
return True
res = 0
for i in range(n):
if ~color[i]:
continue
cnt = [0, 0]
if not dfs(i, 0):
print(-1)
return
res += fmax(cnt[0], cnt[1])
print(res)
if __name__ == "__main__":
T = 1
T = II()
for _ in range(T):
solve()
