【图论练习】medium

2014年12月20日1,4314

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

 

  • 仰慕者2014年12月20日 下午10:45 回复

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

    #1  
    • hzwer2014年12月20日 下午10:57 回复
      admin

      某同学提供

      #11
  • Costwen2016年11月1日 下午9:42 回复

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

    #2  
    • hzwer2016年11月3日 下午9:21 回复
      admin

      无向图去掉回路不是和有向图一样么

      #21