「图论练习」medium

2014年12月20日1,6594

hzwer蒟蒻刚刚学了点图论,现在他面对一张无向连通图

他想问你

最少添加多少条边,使得任意两点之间有两条无公共边的路(可以有公共点)

 

输入格式

第一行n,m,n个点m条边

接下来m行,每行u,v

表示u到v之间有一条无向边(可能重复描述一条边)

输出格式

一行,答案

 

样例输入

5 5

1 2

2 3

3 4

4 5

4 5

样例输出

1

 

数据范围

20%的数据N<=20, M<=50

40%的数据N<=2000,M<=2000

70%的数据N<=20000,M<=20000

100%的数据N<=50000,M<=50000

题解

缩点后,ans=(度为1的连通块个数+1)/2

 

说点什么

提醒
avatar
Costwen

为什么无向图可以用这种Tarjan。。。不应该用low[to ]>=dfn 的那个吗。。还是说两种是一样的?

仰慕者
仰慕者

巨大题目旁边的这些图片都是哪里来的啊,好好看