DFS C++ solution topological sort


  • 0
    X
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            if (numCourses == 0) return vector<int>(0, 0);
            unordered_map<int, vector<int> > adjacentList;
            vector<int> startList(numCourses, 0);
            for (auto pre : prerequisites) {
                adjacentList[pre.first].push_back(pre.second);
                startList[pre.second]++;
            }
            
            int visitedNodes = 0;
            vector<int> marks(numCourses, 0); // 0 indicates not marked, 1 temporary marked, 2 permanent marked
            vector<int> orders;
            while (visitedNodes < numCourses) {
                //find one unvisited node with indegree == 0
                int startNode = findOneUnvisitedNode(numCourses, startList, marks);
                // if cannot find a startNode, return false;
                if (startNode >= numCourses) return vector<int>(0, 0);
                // dfs from start node
                if (!dfs(startNode, adjacentList, marks, visitedNodes, orders)) return vector<int>(0, 0);
            }
            return orders;
        }
        
        int findOneUnvisitedNode(int numCourses, vector<int>& startList, vector<int>& marks) {
            int startNode = 0;
            for (; startNode < numCourses; startNode++) {
                if (startList[startNode] == 0 && marks[startNode] == 0)
                    break;
            }
            return startNode;
        }
        
        bool dfs (int startNode, unordered_map<int, vector<int> >& adjacentList, vector<int>& marks, int & visitedNodes, vector<int>& orders) {
            if (marks[startNode] == 1) return false;
            if (marks[startNode] == 0) {
                marks[startNode] = 1;
                //visit all adjacent node
                for (auto neighbor : adjacentList[startNode]) {
                    if (!dfs(neighbor, adjacentList, marks, visitedNodes, orders)) return false;
                }
                marks[startNode] = 2;
                orders.push_back(startNode);
                visitedNodes++;
            }
            return true;
        }
    };

Log in to reply
 

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