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 KosarajuSharirSCC 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 KosarajuSharirSCC { 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 final int[] size; // size[id] = number of vertices in component containing v 042 private int count; // number of strongly-connected components 043 044 045 public KosarajuSharirSCC(Digraph G) { 046 047 // compute reverse postorder of reverse graph 048 Digraph R = G.reverse (); 049 DepthFirstOrder dfs = new DepthFirstOrder(R); 050 051 // run DFS on G, using reverse postorder to guide calculation 052 marked = new boolean[G.V()]; 053 id = new int[G.V()]; 054 size = new int[G.V()]; 055 for (int v : dfs.reversePost()) { 056 if (!marked[v]) { 057 dfs(G, v); 058 count++; 059 } 060 } 061 062 // check that id[] gives strong components 063 assert check(G); 064 } 065 066 // DFS on graph G 067 private void dfs(Digraph G, int v) { 068 marked[v] = true; 069 id[v] = count; 070 size[count]++; 071 for (int w : G.adj(v)) { 072 if (!marked[w]) { 073 dfs(G, w); 074 } 075 } 076 } 077 078 // return the number of strongly connected components 079 public int count() { return count; } 080 081 // are v and w strongly connected? 082 public boolean stronglyConnected(int v, int w) { 083 return id[v] == id[w]; 084 } 085 086 // id of strong component containing v 087 public int id(int v) { 088 return id[v]; 089 } 090 091 // does the id[] array contain the strongly connected components? 092 private boolean check(Digraph G) { 093 TransitiveClosure tc = new TransitiveClosure(G); 094 for (int v = 0; v < G.V(); v++) { 095 for (int w = 0; w < G.V(); w++) { 096 if (stronglyConnected(v, w) != (tc.reachable(v, w) && tc.reachable(w, v))) 097 return false; 098 } 099 } 100 return true; 101 } 102 103 public static void main(String[] args) { 104 //args = new String[] { "data/tinyDG.txt" }; 105 args = new String[] { "data/mediumDG.txt" }; 106 107 In in = new In(args[0]); 108 Digraph G = DigraphGenerator.fromIn(in); 109 KosarajuSharirSCC scc = new KosarajuSharirSCC(G); 110 if (!scc.check(G)) throw new Error (); 111 112 // number of connected components 113 int M = scc.count(); 114 StdOut.println(M + " components"); 115 116 // compute list of vertices in each strong component 117 @SuppressWarnings("unchecked") 118 Queue<Integer>[] components = new Queue[M]; 119 for (int i = 0; i < M; i++) { 120 components[i] = new Queue<>(); 121 } 122 for (int v = 0; v < G.V(); v++) { 123 components[scc.id(v)].enqueue(v); 124 } 125 126 // print results 127 for (int i = 0; i < M; i++) { 128 for (int v : components[i]) { 129 StdOut.print(v + " "); 130 } 131 StdOut.println(); 132 } 133 134 } 135 136}