Share my AC code using topological-sort


  • 0
    O
    #define ff first
    #define ss second
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<int> deg(numCourses, 0);
            vector<vector<int> > adj(numCourses, vector<int>());
            for (auto i : prerequisites) {
                adj[i.ss].push_back(i.ff);
                deg[i.ff]++;
            }
            vector<int> ans;
            for (int i = 0; i < numCourses; i++) {
                if (deg[i] == 0) {
                    dfs(deg, adj, ans, i);
                }
            }
            if (ans.size() != numCourses) return vector<int>();
            return ans;
        }
        void dfs(vector<int> &deg, vector<vector<int> > &adj, vector<int> &ans, int i) {
            deg[i]--;
            ans.push_back(i);
            for (auto j : adj[i]) {
                deg[j]--;
                if (deg[j] == 0) {
                    dfs(deg, adj, ans, j);
                }
            }
        }
    };

Log in to reply
 

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