Topological Sort - DFS

shriyanshi24jindal

Mar 29th, 2026

114

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 8.73 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/** Idea: normal DFS, only addition is to add node in stack after completing each path traversal*/
public ArrayList<Integer> topoSort(int V, int[][] edges) {
ArrayList<Integer> res = new ArrayList<>();
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for(int i=0; i<V; i++)
{
adj.add(new ArrayList<Integer>());
}
for(int[] edge : edges)
{
int u = edge[0];
int v = edge[1];
adj.get(u).add(v);
}
Stack<Integer> st = new Stack<>();
boolean[] visited = new boolean[V];
for(int i=0; i<V; i++)
{
if(visited[i] == false)
{
dfs(adj, visited, i, st);
}
}
while(!st.isEmpty())
{
res.add(st.pop());
}
return res;
}
public void dfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, int node, Stack<Integer> st)
{
visited[node] = true;
// traverse all neighbours
for(int v : adj.get(node))
{
if(visited[v] == false)
{
dfs(adj, visited, v, st);
}
}
st.push(node);
}
}

RAW Paste Data Copied

class Solution {
    /** Idea: normal DFS, only addition is to add node in stack after completing each path traversal*/
    public ArrayList<Integer> topoSort(int V, int[][] edges) {
        ArrayList<Integer> res = new ArrayList<>();
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<Integer>());
        }
        
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            
            adj.get(u).add(v);
        }
        
        Stack<Integer> st = new Stack<>();
        boolean[] visited = new boolean[V];
        
        for(int i=0; i<V; i++)
        {
            if(visited[i] == false)
            {
                dfs(adj, visited, i, st);
            }
        }
        
        while(!st.isEmpty())
        {
            res.add(st.pop());
        }
        return res;
    }
    
    public void dfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, int node, Stack<Integer> st)
    {
        visited[node] = true;
        
        // traverse all neighbours
        for(int v : adj.get(node))
        {
            if(visited[v] == false)
            {
                dfs(adj, visited, v, st);
            }
        }
        st.push(node);
    }
}