Simple Retrofitted Java Solution


  • 0
    R

    public class Solution {

    boolean[] visited;
    boolean[] flag;
    List<Integer>[] adjList;    
    
    // oder by labeling
    int[] order;
    int label;
    
    // idea: check if a cycle exists in the graph using dfs
    // idea: label nodes with a decreasing label after visiting them 
    public int[] findOrder(int n, int[][] prerequisites) {
    
        visited = new boolean[n];
        flag = new boolean[n];
        adjList = new List[n];
        
        order = new int[n];
        label = n - 1;
    
        // create adj list from edge list        
        for (int i = 0; i < n; i++) {
            adjList[i] = new ArrayList<Integer>();
        }
        for (int j = 0; j < prerequisites.length; j++) {
            adjList[prerequisites[j][1]].add(prerequisites[j][0]);
        }
    
        // run for each node that wasn't flagged
        for (int i = 0; i < n; i++) {
            if (!flag[i]) {
                if (dfs(i)) {
                    // has cycle
                    return new int[0];
                }
            }
        }
    
        return order;
    }
    
    // return true if found cycle
    boolean dfs(int root) {
    
        visited[root] = true;
    
        for (Integer child : adjList[root]) {
    
            if (visited[child])
                return true;
    
            boolean hasCycle = dfs(child);
            if (hasCycle)
                return true;
        }
        
        visited[root] = false;
    
        // label the nodes
        if (!flag[root])
            order[label--] = root;
    
        flag[root] = true;
    
        return false;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.