【题目大意】给定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)minB+=min(x,y),maxB+=max(x,y),最后输出minBmin_BminB和maxBmax_BmaxB即可
【参考程序】
注册一个 核OJ_核桃编程 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 核OJ_核桃编程 通用账户