java BFS topological sort


  • 0
    2
    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            HashMap<Integer, HashSet<Integer>> edges = new HashMap<Integer, HashSet<Integer>>();
            int[] inDegree = new int[numCourses];
            int[] tOrder = new int[numCourses];
            int tSorted = 0;
            for (int[] e : prerequisites) {
                if (!edges.containsKey(e[1])) {
                    edges.put(e[1], new HashSet<Integer>());
                }
                if (edges.get(e[1]).add(e[0])) {
                    inDegree[e[0]]++;
                }
            }
            Queue<Integer> q = new LinkedList<Integer>();
            for (int i = 0; i < numCourses; i++) {
                if (inDegree[i] == 0) {
                    q.add(i);
                }
            }
            while (!q.isEmpty()) {
                int i = q.remove();
                tOrder[tSorted++] = i;
                if (edges.containsKey(i)) {
                    for (int j : edges.get(i)) {
                        if (--inDegree[j] == 0) {
                            q.add(j);
                        }
                    }
                }
            }
            if (tSorted == numCourses) {
                return tOrder;
            }
            return new int[0];
        }
    }
    

Log in to reply
 

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