Welcome, guest! Login / Register - Why register?
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

Your Name: Code Language: