强连通图构造-kosaraju
怎么说呢
题意:给一个强连通图,保证n > 2 * m,现在需要你删去m-2 * n条边,使得图仍然为一个强连通图。
思路:
强连通图的构造,kosaraju模板题
从1开始跑一棵树出来,再反向建边,再从1跑一棵树出来即可。
另一个思路:
由于每一个点都至少被包含于一个环中,所以我们对于点u,找到任意一个包含点u的环,标记环的边,并将其点并到一个并查集中。再枚举不在
并查集中的点,进行同样的操作,不过对于环中的边,若其两点已经在并查集中,则不需要进行标记。所以新加入一个点,最多新加入两条边。
很不错的一个思路,但是错就错在,对于一个环,其中的点处于一个并查集中,但是对于另一个环,其中的点处于另一个并查集中。这两个并查集不连通,出错。
如何让每个并查集连通起来,成为此思路的关键。