stronglyConnectedComponents强联通分量求法kosarajutarjangabow并查集

3.1 kosaraju算法

https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm 伪代码:

1. For each vertex u of the graph, mark u as unvisited. Let L be empty.
2. For each vertex u of the graph do Visit(u), where Visit(u) is the recursive subroutine:

   If u is unvisited then:

   1. Mark u as visited.
   2. For each out-neighbour v of u, do Visit(v).
   3. Prepend u to L.

   Otherwise do nothing.

3. For each element u of L in order, do Assign(u,u) where Assign(u,root) is the recursive subroutine:

   If u has not been assigned to a component then:

   1. Assign u as belonging to the component whose root is root.
   2. For each in-neighbour v of u, do Assign(v,root).

   Otherwise do nothing.

换句话说&＃xff1a;
主要就是2次dfs&＃xff1a;

• 1 获得G的逆图G’&＃xff0c;对G做一遍dfs获得其逆后序的顶点访问序列
• 2 对于逆后序顶点访问序列&＃xff0c;重复2.1即可
  • 2.1 将最晚完成访问的顶点&＃xff0c;在G’中访问&＃xff0c;能够一遍到达的那些顶点&＃xff0c;就是目标的连通分量&＃xff0c;将相关顶点在逆后序访问序列中移除即可

3.2 Tarjan算法&＃xff08;待续&＃xff09;

参考&＃xff1a; https://www.cnblogs.com/wuchanming/p/4138705.html

3.3 Gabow算法(待续)

参考&＃xff1a; https://www.cnblogs.com/wuchanming/p/4138705.html

具体的例子&＃xff1a;

4 实际题解

4.1 针对无向图连通分量求解

该解题方案实际上为有向图强联通分量求解的一个子集&＃xff0c;无向图即为顶点和顶点之间的边均为双向边。
这里以kosaraju算法为例:

• 1 对于有向图&＃xff0c;一开始我们需要获取dfs的逆序遍历栈&＃xff0c;原因是&＃xff0c;在第二次dfs也就是逆图中的遍历我们可以总是用最晚完成遍历的点去遍历&＃xff0c;如此依赖&＃xff0c;这样的一个遍历就能得到一个连通分量。
• 2 但是针对无向图&＃xff0c;不需要这样&＃xff0c;因为遍历到不能拓展新的节点&＃xff0c;我们就获取到了一个连通分量。

https://leetcode-cn.com/problems/number-of-provinces/
其解法如下&＃xff1a;

class Solution {
public:void dfs(vector<vector<int>>& g, vector<int>& reversePost, vector<bool>& vis, int tarV) {vis[tarV] &＃61; true;for(int j &＃61; 0; j < g.size(); &＃43;&＃43;j) {if(g[tarV][j] !&＃61; 0) {if(!vis[j]) {dfs(g, reversePost, vis, j);}} }reversePost.emplace_back(tarV);}int findCircleNum(vector<vector<int>>& isConnected) {// 获取逆图int n &＃61; isConnected.size();vector<vector<int>> revIsConnected(isConnected);// 由于不是针对有向图&＃xff0c;故不需要这一步// 获取逆序vector<bool> vis(n, false);vector<int> reversePost;// dfs(isConnected, reversePost, vis, 0);// 直接任选一点遍历&＃xff0c;看有几个连通分量即可int ans &＃61; 0; for(int j &＃61; 0; j < isConnected.size(); &＃43;&＃43;j) {if(!vis[j]) {dfs(isConnected, reversePost, vis, j);ans &＃43;&＃43;;} }return ans;}
};// 顺便给一个并查集解法&＃xff1a;
class Solution {public int findCircleNum(int[][] isConnected) {int provinces &＃61; isConnected.length;int[] parent &＃61; new int[provinces];for (int i &＃61; 0; i < provinces; i&＃43;&＃43;) {parent[i] &＃61; i;}for (int i &＃61; 0; i < provinces; i&＃43;&＃43;) {for (int j &＃61; i &＃43; 1; j < provinces; j&＃43;&＃43;) {if (isConnected[i][j] &＃61;&＃61; 1) {union(parent, i, j);}}}int circles &＃61; 0;for (int i &＃61; 0; i < provinces; i&＃43;&＃43;) {if (parent[i] &＃61;&＃61; i) {circles&＃43;&＃43;;}}return circles;}public void union(int[] parent, int index1, int index2) {parent[find(parent, index1)] &＃61; find(parent, index2);}public int find(int[] parent, int index) {if (parent[index] !&＃61; index) {parent[index] &＃61; find(parent, parent[index]);}return parent[index];}
}


4.2 针对有向图连通分量的求解

参考例子