1、基本定義： 圖G(V,E)中，在深度搜索時為每一個節點記錄兩個時間戳，分別是開始掃描的時間d和將其所有子節點全部掃描完的時間f； 定義d(U)為節點集U中d的最小值，定義f(U)為節點集U中f的最大值?；静襟E： 1.對圖G進行深度優先搜索，記錄每個節點的d,f; 2.求圖G的轉置Gt（所有節點不變，邊的方向變反）; 3.按照步驟一所求的節點的f，按照降序，對Gt進行深度優先搜索，得到的深度優先森林，森林中深度為1所形成的每個樹，即為各個強連通分量具體代碼：import java.util.ArrayList;import java.util.

2、LinkedList;import java.util.Scanner;/* * * author Founder * 通過深度優先搜索，查找強連通分量 */public class Main static int time = 0; /時間戳 static ArrayList<Integer> topology; /記錄第一次搜索結果的拓撲排序 public static void main(String args) /* * 輸入方式： * 第一行輸入節點的個數n * 后面n行輸入第n個節點（從0開始數）鏈接的子節點，沒有子節點則直接換行 */ Scanner input =

3、new Scanner(System.in); int n = input.nextInt(); Node nodes = new Noden; topology = new ArrayList<>(); for(int i = 0; i < n; +i) nodesi = new Node(); input.nextLine(); for(int i = 0; i < n; +i) String line = input.nextLine(); if(!line.equals("") String tempIntStr = line.split(&

4、quot; "); for(int j = 0; j < tempIntStr.length; +j) nodesi.addLinkNodes(Integer.parseInt(tempIntStrj); dfs(nodes); /* * 準備第二次深度優先搜索，先構造轉置圖 */ Node secondNodes = new Noden; for(int i = 0; i < n; +i) secondNodesi = new Node(); for(int m = 0; m < n; +m) LinkedList<Integer> linkNodes

5、 = nodesm.getLinkNodes(); for(int q = 0; q < linkNodes.size(); +q) secondNodeslinkNodes.get(q).addLinkNodes(m); /* * 開始第二次搜索 */ secondDfs(secondNodes); public static void dfs(Node nodes) for(int i = 0; i < nodes.length; +i) if(nodesi.getColor() = Node.WHITE) dfsVisit(nodes,i); /* * 主要完成兩個工作：設置

6、顏色，設置時間戳 * 附加工作：記錄拓撲排序數組 * param nodes * param no */ public static void dfsVisit(Node nodes,int no) time+; nodesno.setColor(Node.GRAY); nodesno.setD(time); LinkedList<Integer> linkNodes = nodesno.getLinkNodes(); for(int i = 0; i < linkNodes.size(); +i) Node temp = nodeslinkNodes.get(i); if(

7、temp.getColor() = Node.WHITE) temp.setParent(nodesno); dfsVisit(nodes,linkNodes.get(i); nodesno.setColor(Node.BLACK); topology.add(no); time+; nodesno.setF(time); /* * 與第一次的dfs基本相同，唯一的不同是遍歷順序按照拓撲排序進行 * param nodes 圖G的節點數組 */ public static void secondDfs(Node nodes) for(int i = topology.size() - 1; i

8、 >= 0; -i) if(nodestopology.get(i).getColor() = Node.WHITE) secondDfsVisit(nodes,topology.get(i); /* * 與第一次dfsVisit基本相同，具體有“兩增兩減”，不同點如下： * 1.增加輸出當前結點編號 * 2.不再記錄時間戳（因為后面不會再用到這些數據） * 3.不再記錄拓撲排序（因為后面不會再用到這些數據） * 4.回到優先搜索森林深度為1的節點（即沒有設置父節點的節點）時，輸出換行，代表一個強連通分量的結束 * param nodes 圖G的節點數組 * param no 當前父結點

9、 */ public static void secondDfsVisit(Node nodes,int no) System.out.print(no + " "); nodesno.setColor(Node.GRAY); LinkedList<Integer> linkNodes = nodesno.getLinkNodes(); for(int i = 0; i < linkNodes.size(); +i) Node temp = nodeslinkNodes.get(i); if(temp.getColor() = Node.WHITE) te

10、mp.setParent(nodesno); secondDfsVisit(nodes,linkNodes.get(i); nodesno.setColor(Node.BLACK); if(nodesno.getParent() = null) System.out.println(); class Node public static final int WHITE = 0; public static final int GRAY = 1; public static final int BLACK = 2; private int color = WHITE; private int d

11、 = 0; private int f = 0; private Node parent = null; private LinkedList<Integer> linkNodes = null; public Node() linkNodes = new LinkedList<>(); public int getColor() return color; public void setColor(int color) this.color = color; public int getD() return d; public void setD(int d) thi

12、s.d = d; public int getF() return f; public void setF(int f) this.f = f; public Node getParent() return parent; public void setParent(Node parent) this.parent = parent; public LinkedList<Integer> getLinkNodes() return linkNodes; public void setLinkNodes(LinkedList<Integer> linkNodes) thi

13、s.linkNodes = linkNodes; public void addLinkNodes(int no) linkNodes.add(no); 基本原理： 整個算法圍繞著一個核心思想求解：對于圖G總是從f(U)大的強連通分量指向f(U)小的強連通分量，對于G的轉置Gt，則總是根據第一步算出來的f(U)，從f(U)小的強連通分量指向f(U)大的強連通分量（這里可以這樣理解，因為強連通是雙向可達，所以轉置對于強連通內部沒有影響，對強連通分量之間，則指向關系發生了反轉）。這里關于圖G的f(U)的大小問題，待會會做證明，我們先往下看。現在我們證明，對于圖G總是從f(U)大的強連通分量指向f(U)小的強連通分量，假設存在(u,v)，u屬