001package algs42; 002import stdlib.*; 003import algs13.Queue; 004/* *********************************************************************** 005 * Compilation: javac KosarajuSharirSCC.java 006 * Execution: java KosarajuSharirSCC filename.txt 007 * Dependencies: Digraph.java TransitiveClosure.java StdOut.java In.java 008 * Data files: http://algs4.cs.princeton.edu/42directed/tinyDG.txt 009 * 010 * Compute the strongly-connected components of a digraph using the 011 * Kosaraju-Sharir algorithm. 012 * 013 * Runs in O(E + V) time. 014 * 015 * % java KosarajuSCC tinyDG.txt 016 * 5 components 017 * 1 018 * 0 2 3 4 5 019 * 9 10 11 12 020 * 6 021 * 7 8 022 * 023 * % java KosarajuSharirSCC mediumDG.txt 024 * 10 components 025 * 21 026 * 2 5 6 8 9 11 12 13 15 16 18 19 22 23 25 26 28 29 30 31 32 33 34 35 37 38 39 40 42 43 44 46 47 48 49 027 * 14 028 * 3 4 17 20 24 27 36 029 * 41 030 * 7 031 * 45 032 * 1 033 * 0 034 * 10 035 * 036 *************************************************************************/ 037 038public class XKosarajuSharirReverseSCC { 039 private final boolean[] marked; // marked[v] = has vertex v been visited? 040 private final int[] id; // id[v] = id of strong component containing v 041 private int count; // number of strongly-connected components 042 043 044 public XKosarajuSharirReverseSCC(Digraph G) { 045 046 // compute reverse postorder of graph 047 Digraph R = G.reverse (); 048 DepthFirstOrder dfs = new DepthFirstOrder(G); 049 050 // run DFS on G.reverse(), using reverse postorder to guide calculation 051 marked = new boolean[G.V()]; 052 id = new int[G.V()]; 053 for (int v : dfs.reversePost()) { 054 if (!marked[v]) { 055 dfs(R, v); 056 count++; 057 } 058 } 059 060 // check that id[] gives strong components 061 assert check(G); 062 } 063 064 // DFS on graph G 065 private void dfs(Digraph G, int v) { 066 marked[v] = true; 067 id[v] = count; 068 for (int w : G.adj(v)) { 069 if (!marked[w]) dfs(G, w); 070 } 071 } 072 073 // return the number of strongly connected components 074 public int count() { return count; } 075 076 // are v and w strongly connected? 077 public boolean stronglyConnected(int v, int w) { 078 return id[v] == id[w]; 079 } 080 081 // id of strong component containing v 082 public int id(int v) { 083 return id[v]; 084 } 085 086 // does the id[] array contain the strongly connected components? 087 private boolean check(Digraph G) { 088 TransitiveClosure tc = new TransitiveClosure(G); 089 for (int v = 0; v < G.V(); v++) { 090 for (int w = 0; w < G.V(); w++) { 091 if (stronglyConnected(v, w) != (tc.reachable(v, w) && tc.reachable(w, v))) 092 return false; 093 } 094 } 095 return true; 096 } 097 098 public static void main(String[] args) { 099 //args = new String[] { "data/tinyDG.txt" }; 100 args = new String[] { "data/mediumDG.txt" }; 101 102 In in = new In(args[0]); 103 Digraph G = DigraphGenerator.fromIn(in); 104 XKosarajuSharirReverseSCC scc = new XKosarajuSharirReverseSCC(G); 105 if (!scc.check(G)) throw new Error (); 106 107 // number of connected components 108 int M = scc.count(); 109 StdOut.println(M + " components"); 110 111 // compute list of vertices in each strong component 112 @SuppressWarnings("unchecked") 113 Queue<Integer>[] components = new Queue[M]; 114 for (int i = 0; i < M; i++) { 115 components[i] = new Queue<>(); 116 } 117 for (int v = 0; v < G.V(); v++) { 118 components[scc.id(v)].enqueue(v); 119 } 120 121 // print results 122 for (int i = 0; i < M; i++) { 123 for (int v : components[i]) { 124 StdOut.print(v + " "); 125 } 126 StdOut.println(); 127 } 128 129 } 130 131}