001package algs42; 002import stdlib.*; 003import algs13.Queue; 004/* *********************************************************************** 005 * Compilation: javac BruteSCC.java 006 * Dependencies: Digraph.java TransitiveClosure.java 007 * 008 * Compute the strongly-connected components of a digraph using 009 * brute force. 010 * 011 * Runs in O(EV) time. 012 * 013 * % java BruteSCC tinyDG.txt 014 * 5 components 015 * 0 2 3 4 5 016 * 1 017 * 6 018 * 7 8 019 * 9 10 11 12 020 * 021 *************************************************************************/ 022 023public class XBruteSCC { 024 private int count; // number of strongly connected components 025 private final int[] id; // id[v] = id of strong component containing v 026 027 public XBruteSCC(Digraph G) { 028 029 // initially each vertex is in its own component 030 id = new int[G.V()]; 031 for (int v = 0; v < G.V(); v++) 032 id[v] = v; 033 034 // compute transitive closure 035 TransitiveClosure tc = new TransitiveClosure(G); 036 037 // if v and w are mutally reachable, assign v to w's component 038 for (int v = 0; v < G.V(); v++) 039 for (int w = 0; w < v; w++) 040 if (tc.reachable(v, w) && tc.reachable(w, v)) 041 id[v] = id[w]; 042 043 // compute number of strongly connected components 044 for (int v = 0; v < G.V(); v++) 045 if (id[v] == v) 046 count++; 047 } 048 049 // return the number of strongly connected components 050 public int count() { return count; } 051 052 // are v and w strongly connected? 053 public boolean stronglyConnected(int v, int w) { 054 return id[v] == id[w]; 055 } 056 057 // in which strongly connected component is vertex v? 058 public int id(int v) { return id[v]; } 059 060 061 public static void main(String[] args) { 062 args = new String[] { "data/tinyDG.txt" }; 063 064 In in = new In(args[0]); 065 Digraph G = DigraphGenerator.fromIn(in); 066 XBruteSCC scc = new XBruteSCC(G); 067 068 // number of connected components 069 int M = scc.count(); 070 StdOut.println(M + " components"); 071 072 // compute list of vertices in each strong component 073 @SuppressWarnings("unchecked") 074 final 075 Queue<Integer>[] components = new Queue[G.V()]; 076 for (int i = 0; i < G.V(); i++) { 077 components[i] = new Queue<>(); 078 } 079 for (int v = 0; v < G.V(); v++) { 080 components[scc.id(v)].enqueue(v); 081 } 082 083 // print results 084 for (int i = 0; i < G.V(); i++) { 085 if (!components[i].isEmpty()) { 086 for (int v : components[i]) { 087 StdOut.print(v + " "); 088 } 089 StdOut.println(); 090 } 091 } 092 093 } 094 095}