C++, 16ms, topological sort solution,


  • 0

    Standard topological sort solution. Could be used in another questions. Each node maintenance a pair<int,vector<int>> ,first element is the in-degree, second element used to store the children node. when the in-degree equal to zero, means this course could be finished. then decrease its children node in-degree.

    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<pair<int, vector<int>>> adjacent(numCourses, make_pair(0,vector<int>()));
            for(auto & p : prerequisites)
            {
                adjacent[p.second].second.push_back(p.first);
                adjacent[p.first].first++;
            }
            queue<int> course;
            for(int i = 0;i < numCourses;i++)
            {
                if(adjacent[i].first == 0)
                    course.push(i);
            }
            vector<int> res;
            while(!course.empty())
            {
                int tmp = course.front();
                course.pop();
                res.push_back(tmp);
                for(auto n : adjacent[tmp].second)
                {
                    adjacent[n].first--;
                    if(adjacent[n].first == 0)
                    {
                        course.push(n);
                    }
                }
            }
            if(res.size() < numCourses)
                return vector<int>();
            return res; 
        }
    

Log in to reply
 

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