package graph;

import java.util.HashMap;
import java.util.Map;

public class KosarajuSharir<V> {

	private final Graph<V> g;
	private int nc;
	private Map<V, Integer> num = new HashMap<>();

	public KosarajuSharir(Graph<V> g) {
		this.g = g;
	}
	
	private void dfs(V v) {
		if (this.num.containsKey(v)) return;
    this.num.put(v, this.nc);
    for (V w : this.g.successors(v))
      dfs(w);
	}
  
	public Map<V, Integer> components() {
    PostOrder<V> po = new PostOrder<V>(g.reverse());
		for (V v: po.order()) {
			if (num.containsKey(v)) continue;
      dfs(v);
      this.nc++;
		}
		return this.num;
	}
	
}

class TestKosarajuSharir {
	
  public static void main(String[] args) {
    Graph<Integer> g = new Graph<Integer>();
    /* 1 -> 2    3
     * |  /^|  / |
     * V /  V V  V
     * 4 <- 5    6)
     */
    for (int i = 1; i <= 6; i++) g.addVertex(i);
    g.addEdge(1, 2); g.addEdge(1, 4); 
    g.addEdge(2, 5);
    g.addEdge(3, 5); g.addEdge(3, 6);
    g.addEdge(4, 2);
    g.addEdge(5, 4);
    g.addEdge(6, 6);

    KosarajuSharir<Integer> ks = new KosarajuSharir<>(g);
    System.out.println(ks.components());

    // exemple G2 poly
    g = new Graph<Integer>();
    for (int i = 0; i <= 7; i++) g.addVertex(i);
    g.addEdge(1, 0); g.addEdge(1, 2); 
    g.addEdge(2, 1); g.addEdge(2, 3); 
    g.addEdge(3, 4);
    g.addEdge(4, 2);
    g.addEdge(5, 3);
    g.addEdge(6, 4); g.addEdge(6, 7);
    g.addEdge(7, 5); g.addEdge(7, 6);
    ks = new KosarajuSharir<>(g);
    System.out.println(ks.components());

  }
	
}