fork(4) download
copy 
  1. public class KosarajuSharirSCC {
  2.     private boolean[] marked;     // marked[v] = has vertex v been visited?
  3.     private int[] id;             // id[v] = id of strong component containing v
  4.     private int count;            // number of strongly-connected components
  5.  
  6.     /**
  7.      * Computes the strong components of the digraph <tt>G</tt>.
  8.      * @param G the digraph
  9.      */
  10.     public KosarajuSharirSCC(Digraph G) {
  11.  
  12.         // compute reverse postorder of reverse graph
  13.         DepthFirstOrder dfs = new DepthFirstOrder(G.reverse());
  14.  
  15.         // run DFS on G, using reverse postorder to guide calculation
  16.         marked = new boolean[G.V()];
  17.         id = new int[G.V()];
  18.         for (int v : dfs.reversePost()) {
  19.             if (!marked[v]) {
  20.                 dfs(G, v);
  21.                 count++;
  22.             }
  23.         }
  24.  
  25.         // check that id[] gives strong components
  26.         assert check(G);
  27.     }
  28.  
  29.     // DFS on graph G
  30.     private void dfs(Digraph G, int v) { 
  31.         marked[v] = true;
  32.         id[v] = count;
  33.         for (int w : G.adj(v)) {
  34.             if (!marked[w]) dfs(G, w);
  35.         }
  36.     }
  37.  
  38.     /**
  39.      * Returns the number of strong components.
  40.      * @return the number of strong components
  41.      */
  42.     public int count() {
  43.         return count;
  44.     }
  45.  
  46.     /**
  47.      * Are vertices <tt>v</tt> and <tt>w</tt> in the same strong component?
  48.      * @param v one vertex
  49.      * @param w the other vertex
  50.      * @return <tt>true</tt> if vertices <tt>v</tt> and <tt>w</tt> are in the same
  51.      *     strong component, and <tt>false</tt> otherwise
  52.      */
  53.     public boolean stronglyConnected(int v, int w) {
  54.         return id[v] == id[w];
  55.     }
  56.  
  57.     /**
  58.      * Returns the component id of the strong component containing vertex <tt>v</tt>.
  59.      * @param v the vertex
  60.      * @return the component id of the strong component containing vertex <tt>v</tt>
  61.      */
  62.     public int id(int v) {
  63.         return id[v];
  64.     }
  65.  
  66.     // does the id[] array contain the strongly connected components?
  67.     private boolean check(Digraph G) {
  68.         TransitiveClosure tc = new TransitiveClosure(G);
  69.         for (int v = 0; v < G.V(); v++) {
  70.             for (int w = 0; w < G.V(); w++) {
  71.                 if (stronglyConnected(v, w) != (tc.reachable(v, w) && tc.reachable(w, v)))
  72.                     return false;
  73.             }
  74.         }
  75.         return true;
  76.     }
  77.  
  78.     /**
  79.      * Unit tests the <tt>KosarajuSharirSCC</tt> data type.
  80.      */
  81.     public static void main(String[] args) {
  82.         In in = new In(args[0]);
  83.         Digraph G = new Digraph(in);
  84.         KosarajuSharirSCC scc = new KosarajuSharirSCC(G);
  85.  
  86.         // number of connected components
  87.         int M = scc.count();
  88.         StdOut.println(M + " components");
  89.  
  90.         // compute list of vertices in each strong component
  91.         Queue<Integer>[] components = (Queue<Integer>[]) new Queue[M];
  92.         for (int i = 0; i < M; i++) {
  93.             components[i] = new Queue<Integer>();
  94.         }
  95.         for (int v = 0; v < G.V(); v++) {
  96.             components[scc.id(v)].enqueue(v);
  97.         }
  98.  
  99.         // print results
  100.         for (int i = 0; i < M; i++) {
  101.             for (int v : components[i]) {
  102.                 StdOut.print(v + " ");
  103.             }
  104.             StdOut.println();
  105.         }
  106.  
  107.     }
  108.  
  109. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nTZ0nV
language:
Text (text 6.10)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!