首页 > 代码库 > Road Construction
Road Construction
【题目描述】
某岛屿上有N个旅游景点,任意两个旅游景点之间能够连通,但道路部门正在对某条道路进行施工,禁止游客通行,为了使所有旅游景点依然能够正常开放,道路部门决定搭建一些临时桥梁,使得无论哪条道路正在进行施工,游客都能够到达所有的旅游景点。
现询问至少搭建多少条临时桥梁,在施工期间,游客也能够到达所有的旅游景点。
【输入描述】
第一行输入两个整数N、M(N、M <= 1000),表示景点数目以及道路数目;
接下来M行,每行输入两个整数A、B,表示景点A、B之间存在一条直连道路。
【输出描述】
输出一个数,表示答案。
【输入样例】
样例1:
10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10
样例2:
3 3
1 2
2 3
1 3
【输出样例】
样例1:
2
样例2:
0
Road Construction
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。