|
|
back to boardответ Posted by bahasdu 17 Aug 2011 20:06 package topological_sorting; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.LinkedList; import java.util.StringTokenizer; public class Main { public static BufferedReader in; public static PrintWriter out; public static LinkedList<Integer> L; // list of ordered nodes public static LinkedList<Integer> S;// list of nodes which doesn't have // unvisited parent public static void main(String args[]) throws IOException { L = new LinkedList<Integer>(); S = new LinkedList<Integer>(); BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); // input // source int size = (int) Integer.parseInt(in.readLine());// number of members in // meeting int a[][] = new int[size][size];// view.row-numeration of // members.column-whether certain row // has member as child int b[][] = new int[size][size];// view2.it is as // view.column-node.rows-nodes as parent // of column node read(a, in, size);// fill view fillView2(a, b); setNodes(b); // nodes without incoming edges while (S.size() != 0) { int node = (int) S.remove(); L.add(node); for(int j=0;j<a[node-1].length;j++){ if(a[node-1][j]==0){ break; }else{ int childNode = a[node-1][j]; b[node-1][childNode-1]=0; if(!hasParent(b,childNode)){ S.add(childNode); } } } } showList(L); } private static boolean hasParent(int b[][],int node){ boolean hasParent = false; for(int i=0;i<b.length;i++){ if(b[i][node-1]!=0){ hasParent=true; break; } } return hasParent; } private static void showList(LinkedList<Integer> l2) { for (int i = 0; i < l2.size(); i++) { System.out.print(l2.get(i) + " "); } System.out.println(); } private static void setNodes(int[][] b) { for (int j = 0; j < b[0].length; j++) { for (int i = 0; i < b.length; i++) { if (b[i][j] == 0) { if (i == b.length - 1) { S.add(j + 1); } } else { break; } } } } private static void fillView2(int[][] a, int[][] b) { for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (a[i][j] == 0) { break; } else { b[i][a[i][j] - 1] = 1; } } } } // fill view with data private static void read(int[][] a, BufferedReader in, int size) throws IOException { int iterator = 0; while (iterator < size) { StringTokenizer tokenizer = new StringTokenizer(in.readLine()); int j = 0; while (tokenizer.hasMoreTokens()) { a[iterator][j] = (int) Integer.parseInt(tokenizer.nextToken()); j++; } iterator++; } } // observe view public static void showArray(int a[][]) { for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { System.out.print(a[i][j] + " "); } System.out.println(); } } } |
|
|