有那些做任务的网站,宁波网站设计皆选蓉胜网络,重庆展示型网站制作,创新设计案例100个目录 一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解 一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
1594D - The Number of Imposters 二、解题报告
1、思路分析
并查集…目录 一、题目
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()
