What connects us all? Well, it must be the Internet nowadays. With access to the Internet, we can play games, watch drama series, chat with friends, shop online, and order takeout conveniently. Who can ever imagine life without the Internet?
A network is composed of hosts and data links. The hosts refer to terminal devices such as personal computers, mobile phones, and servers, as well as other network devices including switches and routers. A data link is a direct connection between two hosts, over which the data packets can be transmitted in either direction. Data links can be implemented in various physical forms; the most common ones are copper cables, optical fibers, and radio waves, to name but a few.
Since it is generally not practical to build data links between every pair of hosts, the data packets may pass through intermediate hosts when the source host and the destination host are not adjacent. There are many possible routes between two hosts, so we need a routing protocol to decide which route to use. The simplest routing protocol is the Spanning Tree Protocol (STP). In STP, only a subset of all data links are enabled such that every two hosts are reachable and there is no cycle in the enabled data links. The set of enabled data links is called a spanning tree, and it is clear that there is a unique path composed of only enabled data links between any two hosts.
The Network Construction Company have just set up a network, and they want to test whether all data links work properly. To do this, they plan to carry out several rounds of testing. In each round of testing, a spanning tree is chosen and the packages are transmitted via only the data links in the spanning tree, so that the connectivity of every enabled data link can be tested. They want to minimize the number of testing rounds conducted, under the premise that every data link in the network is tested in at least one round.
3502: Network Test
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $1$ | 正确数量 | $0$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
Description
Input
The first line of the input consists of only a single integer T![]()
(1≤T≤50)![]()
, indicating the number of test cases.
Each test case begins with two integers n,m![]()
(2≤n≤1000,1≤m≤2000)![]()
, where n![]()
is the number of hosts and m![]()
is the number of data links. Then follow m![]()
lines, each containing two integers u,v![]()
(1≤u,v≤n,u≠v)![]()
, denoting a data link between two hosts numbered u![]()
and v![]()
. There may be more than one data link between a pair of hosts. It is guaranteed that every two hosts are reachable via the given data links.
There are no more than 20 test cases with m>500![]()
.
Each test case begins with two integers n,m
There are no more than 20 test cases with m>500
Output
For each test case, print the minimum number of rounds conducted as an integer in a single line.
Sample Input复制
2
3 3
1 2
2 3
3 1
4 7
1 3
1 2
1 4
3 2
3 4
2 4
4 2
Sample Output复制
2
3
推荐代码 查看3502 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$ $ms] | |||
| 内存最少[$ $KB] | |||
| 第一AC | |||
| 第一挑战 | ꧁༺ 看看我的名字是不是很长 ༻꧂ | 645514 | 2020-11-02 12:40:10 |
赛题来源/所属竞赛 2020 Multi-University Training Contest 10 N/A
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|