话说这道题的机遇是看到了http://blog.csdn.net/u010885899/article/details/50611895很有意思;然后就去补了这题

题意:

建最少的边使得给出的点相连。

思路:

直观感觉,如果a->b,b->c,那么a->c就不用建了。

然后还有一种情况就是回路a->b->c->a,这样的话要有n条。

所以其实思路就是这样,弱连通的时候n个点就是+n-1条边,强连通的时候n个点+n条边;

印象中tarjan当是这样一条(a->b,b->c)路的时候,操作好就是三个独立的点作为“分量”。

首先对于一个回路,求强连通分量的点的个数,开个数组记录一下就好了。

缩点,形成一张有向无环图DAG。

在DAG上处理就利用并查集把图都弄成独立的几个集合,处理使所有点都与某一个根结点相连,然后判断

//如果这个集合是由独立的点集合,那么就是ans+=num[root]-1;

//如果这个集合有环存在,那么就是ans+=num[root];

具体实现还是比较生疏困难:

1.缩点;

2.DAG上并集,然后更新根结点的数量。

最新文章

  1. Zabbix监控redis status
  2. Theano printing
  3. Python学习笔记1-数据类型
  4. JS中的prototype
  5. 无法打开登录所请求的数据库 "xxx"登录失败用户 'NT AUTHORITY\NETWORK SERVICE'
  6. 理解JavaScript原型式继承
  7. iOS启动图片适配问题
  8. 【解决】hbase regionserver意外关机启动失败 [main] mortbay.log: tmpdir java.io.IOException: Permission denied
  9. PE File.
  10. Python的虚拟环境
  11. [Be a Coding Plasterer] Components 1:get Basic Things
  12. Controller层aop
  13. Papers | 图像/视频增强 + 深度学习
  14. 【PAT】B1052 卖个萌(20 分)
  15. AngularJS中处理多个promise
  16. oracle数据库occi接口写入中文乱码解决方法
  17. 玩转X-CTR100 l STM32F4 l OLED显示-SSD1306无字库
  18. Vue的实时时间转换Demo
  19. Memcachedclient-XMemcached使用
  20. PowerDNS Authoritative Server 3.3 发布

热门文章

  1. ArrayList概述
  2. 功能强大的Xcode辅助工具Faux Pas:帮你找到各种隐形的bug
  3. 【BZOJ3837】[Pa2013]Filary 随机化神题
  4. Local Response Normalization 60 million parameters and 500,000 neurons
  5. eclipse调试第三方jar包需要源码的问题
  6. DuiLib笔记之CDuiString的bug
  7. SAP 系统账期开关
  8. [noip2014day1-T2]联合权值
  9. CSU - 1803 —— 数学题
  10. php排序方法之快速排序