C++ 16ms DFS with explanation


  • 0
    C

    This problem can be abstracted as a graph problem. A pair of prerequisite [u, v] can be considered as a directed edge v -> u.
    It is feasible to crack this problem using Topological Sorting. And DFS method is straightforward.
    Stack s records visited nodes in appropriate order. To detect cycle, in_path remembers all the visited nodes till the current node in the fly. If a node is already true in in_path, it means a cycle existing.

    class Solution {
    public:
        vector<int> findOrder(int n, vector<pair<int, int>>& p) {
            vector<int> res;
            vector<vector<int>> edges (n, vector<int> ());
            vector<bool> visited (n, false);
            vector<bool> in_path (n, false);
            stack<int> s;
            for (auto & i : p) edges[i.second].push_back(i.first);
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    in_path[i] = true;
                    if (!DFS(i, n, edges, visited, s, in_path)) {
                        return res;
                    }
                    in_path[i] = false;
                }
            }
            while (!s.empty()) {
                res.push_back(s.top());
                s.pop();
            }
            return res;
        }
    private:
        // return false if there is a cycle
        bool DFS (int u, int n, vector<vector<int>>& edges, vector<bool> & visited, stack<int>& s, vector<bool>& in_path) {
            visited[u] = true;
            for (int i = 0; i < edges[u].size(); i++) {
                if (in_path[edges[u][i]] == true) return false;
                in_path[edges[u][i]] = true;
                if (!visited[edges[u][i]]) {
                    if (!DFS(edges[u][i], n, edges, visited, s, in_path)) return false;
                }
                in_path[edges[u][i]] = false;
            }
            s.push(u);
            return true;
        }
    };
    

Log in to reply
 

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