01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 package algs42; import stdlib.*; import algs13.Queue; /* *********************************************************************** * Compilation: javac BruteSCC.java * Dependencies: Digraph.java TransitiveClosure.java * * Compute the strongly-connected components of a digraph using * brute force. * * Runs in O(EV) time. * * % java BruteSCC tinyDG.txt * 5 components * 0 2 3 4 5 * 1 * 6 * 7 8 * 9 10 11 12 * *************************************************************************/ public class XBruteSCC { private int count; // number of strongly connected components private final int[] id; // id[v] = id of strong component containing v public XBruteSCC(Digraph G) { // initially each vertex is in its own component id = new int[G.V()]; for (int v = 0; v < G.V(); v++) id[v] = v; // compute transitive closure TransitiveClosure tc = new TransitiveClosure(G); // if v and w are mutally reachable, assign v to w's component for (int v = 0; v < G.V(); v++) for (int w = 0; w < v; w++) if (tc.reachable(v, w) && tc.reachable(w, v)) id[v] = id[w]; // compute number of strongly connected components for (int v = 0; v < G.V(); v++) if (id[v] == v) count++; } // return the number of strongly connected components public int count() { return count; } // are v and w strongly connected? public boolean stronglyConnected(int v, int w) { return id[v] == id[w]; } // in which strongly connected component is vertex v? public int id(int v) { return id[v]; } public static void main(String[] args) { args = new String[] { "data/tinyDG.txt" }; In in = new In(args[0]); Digraph G = DigraphGenerator.fromIn(in); XBruteSCC scc = new XBruteSCC(G); // number of connected components int M = scc.count(); StdOut.println(M + " components"); // compute list of vertices in each strong component @SuppressWarnings("unchecked") final Queue[] components = new Queue[G.V()]; for (int i = 0; i < G.V(); i++) { components[i] = new Queue<>(); } for (int v = 0; v < G.V(); v++) { components[scc.id(v)].enqueue(v); } // print results for (int i = 0; i < G.V(); i++) { if (!components[i].isEmpty()) { for (int v : components[i]) { StdOut.print(v + " "); } StdOut.println(); } } } }