C++ DFS solution and BFS solution


  • 0
    L

    DFS solution:

    #define WHITE 0
    #define GRAY 1
    #define BLACK 2

    class Gragh {
    public: 
     friend class Solution;
     Gragh(int nums) : Vnums(nums), cycle(false) {
            adj = vector<vector<int>>(nums, vector<int>());
            visited = vector<int>(nums, WHITE);
        }
    private: 
        int Vnums;
        bool cycle;
        vector<vector<int>> adj;
        vector<int> visited;
       
        void addEdge(int u, int v) {
            adj[u].push_back(v);
        }
        vector<int> schedule() {
            vector<int> result;
            for (int i = 0; i < Vnums; i++) {
                if (cycle) return vector<int>();
                if (!cycle && visited[i] == WHITE) dfs(i, result);
            }
            if (result.size() != Vnums) return vector<int>();
            else return result;
        }
        void dfs(int node, vector<int> &result) {
            visited[node] = GRAY;
            for (int i = 0; i < adj[node].size(); i++) {
                if (visited[adj[node][i]] == GRAY) { cycle = true; return;}
                if (visited[adj[node][i]] == WHITE) dfs(adj[node][i], result);
            }
            result.insert(result.begin(), node);
            visited[node] = BLACK;
        }
    };
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prer) {
        Gragh myGragh(numCourses);
        for (auto item : prer)
            myGragh.addEdge(item.second, item.first);
        return myGragh.schedule();
    }
    

    BFS solution:

     class Gragh {
    public: 
        int Vnums;
        vector<vector<int>> adj;
        vector<int> indegree;
        Gragh(int nums) : Vnums(nums) {
            adj = vector<vector<int>>(nums, vector<int>());
            indegree = vector<int>(nums, 0);
        }
        void addEdge(int u, int v) {
            adj[u].push_back(v);
        }
        vector<int> schedule() {
            vector<int> result;
            queue<int> myQ;
            for (int i = 0; i < Vnums; i++) {
                if (indegree[i] == 0) myQ.push(i);
            }
            while (!myQ.empty()){
                result.push_back(myQ.front());
                myQ.pop();
                for (auto item : adj[result.back()]) {
                    --indegree[item];
                    if (indegree[item] == 0) myQ.push(item);
                }
            }
            if (result.size() != Vnums) return vector<int>();
            else return result;
        }
    };
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prer) {
        Gragh myGragh(numCourses);
        for (auto item : prer) {
            myGragh.addEdge(item.second, item.first);
            ++(myGragh.indegree[item.first]);
        }
        return myGragh.schedule();
    }

Log in to reply
 

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