5848: [洛谷CSP-S 初赛2024完善程序1]:最小垄断集

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

你有一张 n 个结点(结点编号从 1 n),m 条边的无向无权图

G=(V,E),其中 V 为点集,E 为边集。称 V 的一个子集 S 垄断了图 G,当且仅当 ∀(u,v) ∈ Eu,v 中必然恰有一个结点在 S 内。求垄断了 G 的子集 S 至少有多少个元素,或报告不存在这 样的子集。试补全程序。

输入样例 复制

4 3
1 2
2 3
3 4

输出样例 复制

2