题目 3207

「Cable TV Network」 有线电视网络

查看题解 ↗GitHub ↗如何评测
题号
3207
时间限制
1000 ms
内存限制
128 MB
标签
图论网络流

给定一张n个点m条边的无向图,求最少去掉多少个点,可以使图不连通。

如果不管去掉多少个点,都无法使原图不连通,则直接返回n。

输入格式

输入包含多组测试数据。

每组数据占一行,首先包含两个整数n和m,接下来包含m对形如(x,y)的数对,形容点x与点y之间有一条边。

数对(x,y)中间不会包含空格,其余地方用一个空格隔开。

输出格式

每组数据输出一个结果,每个结果占一行。

数据范围

0≤n≤500 \le n \le 50

输入样例:

文本
0 0
1 0
3 3 (0,1) (0,2) (1,2)
2 0
5 7 (0,1) (0,2) (1,3) (1,2) (1,4) (2,3) (3,4)

输出样例:

文本
0
1
3
0
2

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解

数据下载

题目 3207 的公开数据

正在读取文件列表…

常用命令

题目 3207 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。