Psst.. new poll here.
Psst.. new forums here.
Microsoft is blocking us again (TY IP Reputation!) so just use oauth login instead. :)
Paste
Pasted as Java by Hashit ( 6 years ago )
import java.io.*;
import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int n= Integer.parseInt(input[0]);
int m= Integer.parseInt(input[1]);
LinkedList<Integer>[] adjList= new LinkedList[n+1];
LinkedList<Integer>[] adjListReverse= new LinkedList[n+1];
for(int i=0;i<=n;i++){
adjList[i]= new LinkedList<>();
adjListReverse[i]= new LinkedList<>();
}
for(int i=0;i<m;i++){
input = br.readLine().split(" ");
int u= Integer.parseInt(input[0]);
int v= Integer.parseInt(input[1]);
adjList[u].add(v);
// adjListReverse[v].add(u);
}
for(int i=1;i<=n;i++){
LinkedList<Integer> list = adjList[i];
Collections.sort(list,Collections.reverseOrder());
adjList[i]=list;
}
//dfs
Deque<Integer> stack = new ArrayDeque<>();
boolean[] visited= new boolean[n+1];
for(int i=n;i>0;i--){
if(!visited[i]){
firstDFS(adjList,i,stack,visited);
}
}
while(!stack.isEmpty()){
System.out.print(stack.pop()+" ");
}
}
static void firstDFS(LinkedList<Integer>[] adjList,int vertex,Deque<Integer> stack,boolean[] visited){
visited[vertex]=true;
// System.out.print("v="+vertex);
for(Integer adj: adjList[vertex]){
if(!visited[adj]){
// System.out.println("v="+vertex+"adj="+adj);
firstDFS(adjList,adj,stack,visited);
}
}
// System.out.println("pushing in stack v="+vertex);
stack.push(vertex);
}
}
Revise this Paste