# How to get all the solutions of topological sorting

Hi everyone I was trying to solve this problem http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=813 and I realized that it wants to get all the solutions of topological sorting problem, I know how to get only one possible solution and this is my code http://ideone.com/IiQxiu

```static ArrayList<Integer> [] arr;
static int visited [];
static Stack<Integer> a = new Stack<Integer>();
static boolean flag=false;

public static void graphcheck(int node){  //method to check if there is a cycle in the graph
visited[node] = 2;
for(int i=0;i<arr[node].size();i++){
int u =arr[node].get(i);
if(visited[u]==0){
graphcheck(u);
}else if(visited[u]==2){
flag=true;
return;
}
}
visited[node] = 1;
}

public static void dfs2(int node){            //method to get one possible topological sort which I want to extend to get all posibilites
visited[node] = 1;
for(int i=0;i<arr[node].size();i++){
int u =arr[node].get(i);
if(visited[u]==0){
dfs2(u);
}
}
a.push(node);
}

public static void main(String[] args) throws NumberFormatException, IOException {
for(int k=0;k<tc;k++){

int n= h.length;
arr=new ArrayList[n];
visited = new int[n];
for( int i = 0; i < n; i++) {
arr[ i] = new ArrayList<Integer>();
}
int y=q.length;
for(int i=0;i<y;i++){
int x=0;
int z=0;
for(int j=0;j<n;j++){
if(q[i].charAt(0)==h[j].charAt(0)){
x=j;
}else if(q[i].charAt(2)==h[j].charAt(0)){
z=j;
}
}
if(q[i].charAt(1)=='<'){
}
}
for(int i=0;i<n;i++){
if(visited[i]==0)
graphcheck(i);
}
if(flag){
System.out.println("NO");
}else{
a.clear();
Arrays.fill(visited, 0);
for(int i=0;i<n;i++){
if(visited[i]==0){
dfs2(i);
}
}
int z= a.size();
for(int i=0;i<z;i++){
int x =a.pop();
System.out.print(h[x]+" ");
}
System.out.println();
}

}
}
```

A potential way would be to modify the algorithm specified by Khan, (1962), in which a topological sort is calculated using the following algorithm:

L ← Empty list that will contain the sorted elements

S ← Set of all nodes with no incoming edges

while S is non-empty do

```   remove a node n from S

insert n into L

for each node m with an edge e from n to m do

remove edge e from the graph

if m has no other incoming edges then

insert m into S
```

if graph has edges then

```   return error (graph has at least one cycle)
```

else

```   return L (a topologically sorted order)
```

This calculates one topological sort, in order to generate all possible sorts. To get all possible sorts, you could think of the result as a tree, where the root is the first node, and each child of a node is one of the next values. Given a graph:

```    1 -> 3 -> 8
|    |    |
|    v    |
|    7    |
|        |
|      _ v
+--> 5 -> 9
```

The tree might look like:

```        1
/
3   5
/|  |
7 8 9 9
| |
9 9
```