二染色,CF 1594D - The Number of Imposters

目录

一、题目

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()