51nod 1456【强连通,缩点,并查集】

话说这道题的机遇是看到了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上并集,然后更新根结点的数量。

原文地址:https://www.cnblogs.com/keyboarder-zsq/p/5934752.html