import java.util.*;
class GraphAllTopSorts {
int V; // No. of vertices
LinkedList<Integer>[] adj; //Adjacency List
boolean[] marked; //Boolean array to store the visited nodes
List<Integer> list; //
int[] indegree; //integer array to store the indegree of nodes
Stack<Integer> st;
LinkedList<Integer> q;
//Constructor
public GraphAllTopSorts(int v) {
this.V=v;
for (int i=0;i<v;i++) {
adj[i] = new LinkedList<Integer>();
}
this.indegree = new int[v];
this.marked = new boolean[v];
list = new ArrayList<Integer>();
this.st = new Stack<Integer>();
this.q = new LinkedList<Integer>();
}
// function to add an edge to graph
public void addEdge(int v, int w){
adj[v].add(w);
// increasing inner degree of w by 1
indegree[w]++;
}
public void getKosarajuTopologicalSort(int val) {
for (int i=0;i<V;i++) {
if (!marked[i]) {
dfs(i);
}
}
if (val==0) {
while (!q.isEmpty()) {
System.
out.
print(q.
remove() + " "); }
}
else {
while (!st.isEmpty()) {
int w = st.pop();
}
}
}
public void dfs(int v) {
marked[v] = true;
Iterator<Integer> iter = adj[v].listIterator();
while (iter.hasNext()) {
int w = iter.next();
if (!marked[w]) {
dfs(w);
}
}
q.add(v);
st.push(v);
}
public GraphAllTopSorts reverse() {
GraphAllTopSorts g2 = new GraphAllTopSorts(V);
for (int i=0;i<V;i++) {
Iterator<Integer> iter = adj[i].listIterator();
while (iter.hasNext()) {
int w = iter.next();
g2.addEdge(w, i);
}
}
return g2;
}
// Driver program to test above functions
public static void main
(String[] args
) { // Create a graph given in the above diagram
GraphAllTopSorts g = new GraphAllTopSorts(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.
out.
println("PostOrder for original graph"); g.getKosarajuTopologicalSort(0);
System.
out.
println("Kosaraju Topological Sort (Reverse PostOrder) for reverse graph"); GraphAllTopSorts g2 = g.reverse();
g2.getKosarajuTopologicalSort(1);
}
}
aW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgR3JhcGhBbGxUb3BTb3J0cyB7CiAgICBpbnQgVjsgIC8vIE5vLiBvZiB2ZXJ0aWNlcwogICAgTGlua2VkTGlzdDxJbnRlZ2VyPltdIGFkajsgIC8vQWRqYWNlbmN5IExpc3QKICAgIGJvb2xlYW5bXSBtYXJrZWQ7ICAgLy9Cb29sZWFuIGFycmF5IHRvIHN0b3JlIHRoZSB2aXNpdGVkIG5vZGVzCiAgICBMaXN0PEludGVnZXI+IGxpc3Q7IC8vCiAgICBpbnRbXSBpbmRlZ3JlZTsgLy9pbnRlZ2VyIGFycmF5IHRvIHN0b3JlIHRoZSBpbmRlZ3JlZSBvZiBub2RlcwogICAgU3RhY2s8SW50ZWdlcj4gc3Q7CiAgICBMaW5rZWRMaXN0PEludGVnZXI+IHE7CgogICAgLy9Db25zdHJ1Y3RvcgogICAgcHVibGljIEdyYXBoQWxsVG9wU29ydHMoaW50IHYpIHsKICAgICAgICB0aGlzLlY9djsKICAgICAgICB0aGlzLmFkaiA9IG5ldyBMaW5rZWRMaXN0W3ZdOwogICAgICAgIGZvciAoaW50IGk9MDtpPHY7aSsrKSB7CiAgICAgICAgICAgIGFkaltpXSA9IG5ldyBMaW5rZWRMaXN0PEludGVnZXI+KCk7CiAgICAgICAgfQogICAgICAgIHRoaXMuaW5kZWdyZWUgPSBuZXcgaW50W3ZdOwogICAgICAgIHRoaXMubWFya2VkID0gbmV3IGJvb2xlYW5bdl07CiAgICAgICAgbGlzdCA9IG5ldyBBcnJheUxpc3Q8SW50ZWdlcj4oKTsKICAgICAgICB0aGlzLnN0ID0gbmV3IFN0YWNrPEludGVnZXI+KCk7CiAgICAgICAgdGhpcy5xID0gbmV3IExpbmtlZExpc3Q8SW50ZWdlcj4oKTsKICAgIH0KCiAgICAvLyBmdW5jdGlvbiB0byBhZGQgYW4gZWRnZSB0byBncmFwaAogICAgcHVibGljIHZvaWQgYWRkRWRnZShpbnQgdiwgaW50IHcpewogICAgICAgIGFkalt2XS5hZGQodyk7CiAgICAgICAgLy8gaW5jcmVhc2luZyBpbm5lciBkZWdyZWUgb2YgdyBieSAxCiAgICAgICAgaW5kZWdyZWVbd10rKzsKICAgIH0KCiAgICBwdWJsaWMgdm9pZCBnZXRLb3NhcmFqdVRvcG9sb2dpY2FsU29ydChpbnQgdmFsKSB7CiAgICAgICAgZm9yIChpbnQgaT0wO2k8VjtpKyspIHsKICAgICAgICAgICAgaWYgKCFtYXJrZWRbaV0pIHsKICAgICAgICAgICAgICAgIGRmcyhpKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgaWYgKHZhbD09MCkgewogICAgICAgICAgICB3aGlsZSAoIXEuaXNFbXB0eSgpKSB7CiAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50KHEucmVtb3ZlKCkgKyAiICIpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnQoIlxuIik7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICB3aGlsZSAoIXN0LmlzRW1wdHkoKSkgewogICAgICAgICAgICAgICAgaW50IHcgPSBzdC5wb3AoKTsKICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnQodyArICIgIik7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludCgiXG4iKTsKICAgICAgICB9CgogICAgfQoKICAgIHB1YmxpYyB2b2lkIGRmcyhpbnQgdikgewogICAgICAgIG1hcmtlZFt2XSA9IHRydWU7CiAgICAgICAgSXRlcmF0b3I8SW50ZWdlcj4gaXRlciA9IGFkalt2XS5saXN0SXRlcmF0b3IoKTsKICAgICAgICB3aGlsZSAoaXRlci5oYXNOZXh0KCkpIHsKICAgICAgICAgICAgaW50IHcgPSBpdGVyLm5leHQoKTsKICAgICAgICAgICAgaWYgKCFtYXJrZWRbd10pIHsKICAgICAgICAgICAgICAgIGRmcyh3KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBxLmFkZCh2KTsKICAgICAgICBzdC5wdXNoKHYpOwogICAgfQoKICAgIHB1YmxpYyBHcmFwaEFsbFRvcFNvcnRzIHJldmVyc2UoKSB7CiAgICAgICAgR3JhcGhBbGxUb3BTb3J0cyBnMiA9IG5ldyBHcmFwaEFsbFRvcFNvcnRzKFYpOwogICAgICAgIGZvciAoaW50IGk9MDtpPFY7aSsrKSB7CiAgICAgICAgICAgIEl0ZXJhdG9yPEludGVnZXI+IGl0ZXIgPSBhZGpbaV0ubGlzdEl0ZXJhdG9yKCk7CiAgICAgICAgICAgIHdoaWxlIChpdGVyLmhhc05leHQoKSkgewogICAgICAgICAgICAgICAgaW50IHcgPSBpdGVyLm5leHQoKTsKICAgICAgICAgICAgICAgIGcyLmFkZEVkZ2UodywgaSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGcyOwogICAgfQoKICAgIC8vIERyaXZlciBwcm9ncmFtIHRvIHRlc3QgYWJvdmUgZnVuY3Rpb25zCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgLy8gQ3JlYXRlIGEgZ3JhcGggZ2l2ZW4gaW4gdGhlIGFib3ZlIGRpYWdyYW0KICAgICAgICBHcmFwaEFsbFRvcFNvcnRzIGcgPSBuZXcgR3JhcGhBbGxUb3BTb3J0cyg2KTsKICAgICAgICBnLmFkZEVkZ2UoNSwgMik7CiAgICAgICAgZy5hZGRFZGdlKDUsIDApOwogICAgICAgIGcuYWRkRWRnZSg0LCAwKTsKICAgICAgICBnLmFkZEVkZ2UoNCwgMSk7CiAgICAgICAgZy5hZGRFZGdlKDIsIDMpOwogICAgICAgIGcuYWRkRWRnZSgzLCAxKTsKCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJQb3N0T3JkZXIgZm9yIG9yaWdpbmFsIGdyYXBoIik7CiAgICAgICAgZy5nZXRLb3NhcmFqdVRvcG9sb2dpY2FsU29ydCgwKTsKCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJLb3NhcmFqdSBUb3BvbG9naWNhbCBTb3J0IChSZXZlcnNlIFBvc3RPcmRlcikgZm9yIHJldmVyc2UgZ3JhcGgiKTsKICAgICAgICBHcmFwaEFsbFRvcFNvcnRzIGcyID0gZy5yZXZlcnNlKCk7CiAgICAgICAgZzIuZ2V0S29zYXJhanVUb3BvbG9naWNhbFNvcnQoMSk7CgoKICAgIH0KfQ==