001package algs42; 002import stdlib.*; 003import algs13.Queue; 004import algs13.Stack; 005/* *********************************************************************** 006 * Compilation: javac TarjanSCC.java 007 * Execution: Java XTarjanSCC V E 008 * Dependencies: Digraph.java Stack.java TransitiveClosure.java StdOut.java 009 * 010 * Compute the strongly-connected components of a digraph using 011 * Tarjan's algorithm. 012 * 013 * Runs in O(E + V) time. 014 * 015 * % java TarjanSCC 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 *************************************************************************/ 024 025public class XTarjanSCC { 026 027 private final boolean[] marked; // marked[v] = has v been visited? 028 private final int[] id; // id[v] = id of strong component containing v 029 private final int[] low; // low[v] = low number of v 030 private int pre; // preorder number counter 031 private int count; // number of strongly-connected components 032 private final Stack<Integer> stack; 033 034 035 public XTarjanSCC(Digraph G) { 036 marked = new boolean[G.V()]; 037 stack = new Stack<>(); 038 id = new int[G.V()]; 039 low = new int[G.V()]; 040 for (int v = 0; v < G.V(); v++) { 041 if (!marked[v]) dfs(G, v); 042 } 043 044 // check that id[] gives strong components 045 assert check(G); 046 } 047 048 private void dfs(Digraph G, int v) { 049 marked[v] = true; 050 low[v] = pre++; 051 int min = low[v]; 052 stack.push(v); 053 for (int w : G.adj(v)) { 054 if (!marked[w]) dfs(G, w); 055 if (low[w] < min) min = low[w]; 056 } 057 if (min < low[v]) { low[v] = min; return; } 058 int w; 059 do { 060 w = stack.pop(); 061 id[w] = count; 062 low[w] = G.V(); 063 } while (w != v); 064 count++; 065 } 066 067 068 069 // return the number of strongly connected components 070 public int count() { return count; } 071 072 073 // are v and w strongly connected? 074 public boolean stronglyConnected(int v, int w) { 075 return id[v] == id[w]; 076 } 077 078 // in which strongly connected component is vertex v? 079 public int id(int v) { return id[v]; } 080 081 // does the id[] array contain the strongly connected components? 082 private boolean check(Digraph G) { 083 TransitiveClosure tc = new TransitiveClosure(G); 084 for (int v = 0; v < G.V(); v++) { 085 for (int w = 0; w < G.V(); w++) { 086 if (stronglyConnected(v, w) != (tc.reachable(v, w) && tc.reachable(w, v))) 087 return false; 088 } 089 } 090 return true; 091 } 092 093 public static void main(String[] args) { 094 args = new String[] { "data/tinyDG.txt" }; 095 096 In in = new In(args[0]); 097 Digraph G = DigraphGenerator.fromIn(in); 098 XTarjanSCC scc = new XTarjanSCC(G); 099 100 // number of connected components 101 int M = scc.count(); 102 StdOut.println(M + " components"); 103 104 // compute list of vertices in each strong component 105 @SuppressWarnings("unchecked") 106 final 107 Queue<Integer>[] components = new Queue[M]; 108 for (int i = 0; i < M; i++) { 109 components[i] = new Queue<>(); 110 } 111 for (int v = 0; v < G.V(); v++) { 112 components[scc.id(v)].enqueue(v); 113 } 114 115 // print results 116 for (int i = 0; i < M; i++) { 117 for (int v : components[i]) { 118 StdOut.print(v + " "); 119 } 120 StdOut.println(); 121 } 122 123 } 124 125}