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()); } }