Guest User

Untitled

a guest
Jul 22nd, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.41 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5. static boolean[] visited;
  6. static int[] res;
  7. static int index;
  8. static ArrayList<Integer>[] adj;
  9. private static void toposort() {
  10. for(int i=0;i<adj.length;i++) {
  11. explore(i);
  12. }
  13. }
  14. private static void explore(int s) {
  15. if(!visited[s]) {
  16. visited[s]=true;
  17. for(int i=0;i<adj[s].size();i++) {
  18. explore(adj[s].get(i));
  19. }
  20. res[index++]=s;
  21. }
  22. }
  23. public static void main(String[] args) {
  24. Scanner scanner = new Scanner(System.in);
  25. int n = scanner.nextInt();
  26. int m = scanner.nextInt();
  27. while(true) {
  28. adj = (ArrayList<Integer>[])new ArrayList[n];
  29. for (int i = 0; i < n; i++) {
  30. adj[i] = new ArrayList<Integer>();
  31. }
  32. for (int i = 0; i < m; i++) {
  33. int x, y;
  34. x = scanner.nextInt();
  35. y = scanner.nextInt();
  36. adj[y - 1].add(x - 1);
  37. }
  38. visited=new boolean[n];
  39. res=new int[n];
  40. index=0;
  41. toposort();
  42. for(int i=0;i<res.length-1;i++) {
  43. System.out.print(res[i]+1+" ");
  44. }
  45. System.out.println(res[n-1]+1);
  46. n=scanner.nextInt();
  47. m=scanner.nextInt();
  48. if(n==0)
  49. break;
  50. }
  51. scanner.close();
  52. }
  53. }
Add Comment
Please, Sign In to add comment