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 { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int tc = Integer.parseInt(br.readLine()); for(int k=0;k<tc;k++){ br.readLine(); String h[]= br.readLine().split(" "); int n= h.length; arr=new ArrayList[n]; visited = new int[n]; for( int i = 0; i < n; i++) { arr[ i] = new ArrayList<Integer>(); } String q[]=br.readLine().split(" "); 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)=='<'){ arr[x].add(z); } } 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(); } } }

## Answer

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 Sif 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

However, after re-reading your problem:

Given a list of variable constraints of the form A < B, you are to write a program that prints all orderings of the variables that are consistent with the constraints. For example, given the contraints A < B and A < C there are two orderings of the variables A, B and C that are consistent with these constraints: ABC and ACB.

I don’t believe this solution will provide you with the answers you are looking for, but you are more than welcome to try and implement it.

Also check out this algorithm.

*Note:*

I was going to refrain from posting this after re-reading your problem, however I decided against it, as this information may be useful to you.

Good luck.