tarjan之双连通图(无向图)

这里有几个点需要注意
1.为什么无向图缩点需要变成有向图缩点?
无向图两两之间的点可以到达,无法跑回边的话,就跑不到父节点以上的节点了,那么肯定是桥了。
2.为什么不能跑回边,而不是跑父节点?
本来是个无向图单连通,但是你阻止了父节点跑回去,那就不是无向图单连通了。
但是这个题去重也对,嗯[……]

Read more

tarjan算法之无向图求割点

先学tarjan算法,再学割点,优质博客 .

割点也就是把此点去掉后,使无向强连通图至少变成2部分。

1.哪些点是割点?

2.此割点把图割成了几部分?

第一个问题:1.如果根有两个或两个以上的树,那么此点必为割点。

2.如果u不是根节点,它有一个子节点v,并且以v为根节[……]

Read more

tarjan算法之有向图缩点

1.求至少选几个点作为起点走遍全图(也就是这几个点走的路加起来走遍全图)?

2.求最小加多少边能使图变成强连通图?

tarjan缩点求入度为0的点为第一个题的答案,求max(入度为0的点,出度为0的点)为第二个题的答案。

tarjan缩点方法最后给出代码。

疑问:

1.[……]

Read more