1 条题解

  • -1
    @ 2024-6-6 16:35:49

    【题目大意】给定n个点,这些点要么属于A类,要么属于B类,给定m条边,一条边的两个端点必然一个属于A类,另一个属于B类,求属于B类的点的个数可能的最小值和最大值。

    【考纲知识点】图的遍历

    【解题思路】按照题目的输入进行连边,此时可以将整张图分为若干个连通块,对于每一个连通块都进行01染色,设颜色为0和1的点的个数分别为x,y,则B类点的数量即可以是x也可以是y,让 minB+=min(x,y)maxB+=max(x,y)min_B +=min(x,y),max_B+=max(x,y),最后输出minBmin_BmaxBmax_B即可

    【参考程序】

    image

    • 1

    [GESP202403 七级] 交流问题

    信息

    ID
    652
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    4
    已通过
    2
    上传者