C++ Topological Sorting Solution


  • 0
    L
    class Solution {
    public:
        // Kind of like Topological Sort of Directed Graph
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> adj(numCourses);
            vector<int> indegrees(numCourses, 0);
            vector<int> res;
            for (auto prerequisite : prerequisites) {
                if (adj[prerequisite.second].find(prerequisite.first) == adj[prerequisite.second].end()) {
                    indegrees[prerequisite.first]++;
                }
                adj[prerequisite.second].insert(prerequisite.first);
            }
            
            while (res.size() < numCourses) {
                int curr = -1;
                for (int i = 0; i < numCourses; i++) {
                    if (indegrees[i] == 0) {
                        curr = i;
                        break;
                    }
                }
                if (curr == -1) {
                    res.clear();
                    return res;
                }
                for (auto neighbor : adj[curr]) {
                    indegrees[neighbor]--;
                }
                indegrees[curr] = numCourses;
                res.push_back(curr);
            }
            
            return res;
        }
        
        
    };

Log in to reply
 

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