fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.  
  11. 	public static void dfs(int node, ArrayList<ArrayList<Integer>> newGraph, boolean[] vis,ArrayList<Integer>comp){
  12. 		vis[node] = true;
  13. 		comp.add(node);
  14. 		for(int neg : newGraph.get(node)){
  15. 			if(!vis[neg]){
  16. 				dfs(neg, newGraph, vis, comp);
  17. 			}
  18. 		}
  19. 	}
  20.  
  21. 	public static void main (String[] args) throws java.lang.Exception
  22. 	{
  23. 		// your code goes here
  24. 		int N = 8;
  25. 		int[] a = {2, 1, 4, 3, 6, 5, 8, 7};
  26. 		int[] c = {1, 2, 1, 2, 2, 1, 2, 1};
  27.  
  28. 		ArrayList<ArrayList<Integer>> Adj = new ArrayList<>();
  29.  
  30. 		for(int i = 0; i <= N; i++) Adj.add(new ArrayList<>());
  31.  
  32. 		int[] indegree = new int[N + 1];
  33.  
  34. 		for(int i = 0; i < N; i++){
  35. 			int u = i + 1;
  36. 			int v = a[i];
  37. 			Adj.get(u).add(v);
  38. 			indegree[v]++;
  39. 		}
  40.  
  41. 		Queue<Integer> q = new LinkedList<>();
  42.  
  43. 		for(int i = 1; i <= N; i++){
  44. 			if(indegree[i] == 0){
  45. 				q.add(i);
  46. 			}
  47. 		}
  48.  
  49. 		boolean[] sold = new boolean[N + 1];
  50.  
  51. 		ArrayList<Integer> Order = new ArrayList<>();
  52.  
  53. 		while(!q.isEmpty()){
  54. 			int animal = q.poll();
  55. 			Order.add(animal);
  56. 			sold[animal] = true;
  57. 			for(int i : Adj.get(animal)){
  58. 				indegree[i]--;
  59. 				if(indegree[i] == 0) q.add(i);
  60. 			}
  61. 		}
  62.  
  63. 		ArrayList<ArrayList<Integer>> newGraph = new ArrayList<>();
  64.  
  65. 		for(int i = 0; i <= N; i++) newGraph.add(new ArrayList<>());
  66.  
  67. 		for(int i = 0; i < N; i++){
  68. 			if(!sold[i + 1]){
  69. 			int u = i + 1;
  70. 			int v = a[i];
  71. 			newGraph.get(u).add(v);
  72. 			}
  73. 		}
  74.  
  75. 		boolean[] vis = new boolean[N + 1];
  76.  
  77. 		for(int i = 1; i <= N ; i++){
  78. 			if(!vis[i] && !sold[i] && !newGraph.get(i).isEmpty()){
  79. 				ArrayList<Integer> comp = new ArrayList<>();
  80. 				dfs(i, newGraph, vis, comp);
  81.  
  82. 				int minNode = comp.get(0);
  83. 				for(int node : comp){
  84. 					if(c[node - 1] < c[minNode -1]){
  85. 						minNode = node;
  86. 					}
  87. 				}
  88.  
  89. 				int curr = a[minNode - 1];
  90. 				while(curr != minNode){
  91. 					Order.add(curr);
  92. 					sold[curr] = true;
  93. 					curr = a[curr - 1];
  94. 				}
  95. 				Order.add(minNode);
  96. 				sold[minNode] = true;
  97. 				}
  98. 		}
  99.  
  100. 		for(int i : Order) System.out.print(i + " ");
  101. 	}
  102. }
Success #stdin #stdout 0.12s 55544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 1 4 3 5 6 7 8
https://ideone.com/8R7oFL
language:
Java (HotSpot 12)
created:
122 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!