二染色,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 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()

相关推荐

  1. CF988D题解

    2024-07-22 04:08:03       22 阅读
  2. 题解:CF1923D(Slimes)

    2024-07-22 04:08:03       48 阅读
  3. 题解:CF1946D(Birthday Gift)

    2024-07-22 04:08:03       37 阅读
  4. <span style='color:red;'>D</span>3<span style='color:red;'>CTF</span>2024

    D3CTF2024

    2024-07-22 04:08:03      26 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 04:08:03       106 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 04:08:03       116 阅读
  3. 在Django里面运行非项目文件

    2024-07-22 04:08:03       95 阅读
  4. Python语言-面向对象

    2024-07-22 04:08:03       103 阅读

热门阅读

  1. MLIR

    2024-07-22 04:08:03       22 阅读
  2. 周六算法加练

    2024-07-22 04:08:03       26 阅读
  3. qt 数字转字符

    2024-07-22 04:08:03       26 阅读
  4. qt log 输出为文件

    2024-07-22 04:08:03       24 阅读
  5. 谈谈如何快速学习一门技术

    2024-07-22 04:08:03       26 阅读
  6. WebGIS面试题(第八期)

    2024-07-22 04:08:03       21 阅读
  7. 算法的概述

    2024-07-22 04:08:03       22 阅读
  8. 2024年水利水电安全员考试题库及答案

    2024-07-22 04:08:03       25 阅读
  9. c语言(7.21)

    2024-07-22 04:08:03       23 阅读
  10. 原型继承和原型链

    2024-07-22 04:08:03       25 阅读
  11. 【渗透入门】反序列化

    2024-07-22 04:08:03       23 阅读
  12. Windows图形界面(GUI)-DLG-C/C++ - 月历控件(MonthCalendar)

    2024-07-22 04:08:03       25 阅读