51nod 1456【强连通,缩点,并查集】
2024-09-08 11:50:48
话说这道题的机遇是看到了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上并集,然后更新根结点的数量。
最新文章
- Zabbix监控redis status
- Theano printing
- Python学习笔记1-数据类型
- JS中的prototype
- 无法打开登录所请求的数据库 ";xxx";登录失败用户 'NT AUTHORITY\NETWORK SERVICE'
- 理解JavaScript原型式继承
- iOS启动图片适配问题
- 【解决】hbase regionserver意外关机启动失败 [main] mortbay.log: tmpdir java.io.IOException: Permission denied
- PE File.
- Python的虚拟环境
- [Be a Coding Plasterer] Components 1:get Basic Things
- Controller层aop
- Papers | 图像/视频增强 + 深度学习
- 【PAT】B1052 卖个萌(20 分)
- AngularJS中处理多个promise
- oracle数据库occi接口写入中文乱码解决方法
- 玩转X-CTR100 l STM32F4 l OLED显示-SSD1306无字库
- Vue的实时时间转换Demo
- Memcachedclient-XMemcached使用
- PowerDNS Authoritative Server 3.3 发布