Summary-of-2-different-implementations


  • 2

    First of all, this problem is graph-based-topological-sorting problem, so we should consider how to represent graph in C++ code.

    After seeing many posts, most of them use the

      vector<unordered_set<int>> graph
    

    then we initialize the graph based on all the edges. like this

       matrix[node1].insert(node2)
    

    We construct a neighbor-set-based-graph-representation.

    Next, we should count all the in-degree of all the vertex.

    So , we find the topological-order by deleting the node-that-in-degree=0

    Then, update all the related nodes' in-degree.

    simple-loop-based-solution

    Implementation

    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> matrix(numCourses, unordered_set<int>());
            /*** construct the directed graph : (1, 0) means edge:0->1  ***/
            for(int i=0; i<prerequisites.size(); i++)
                matrix[prerequisites[i].second].insert(prerequisites[i].first);
            /*** statistic all the in-degree of all the vertex ***/    
            vector<int> d(numCourses, 0);
            for(int i=0; i<numCourses; i++)
                for(auto it = matrix[i].begin(); it!=matrix[i].end(); it++){
                    d[*it]++;
                }
            
            /*** topological sort ***/   
            for(int j=0, i; j<numCourses; ++j){
                /*** find the node with in-degree=0 ***/
                for(i=0; i<numCourses && d[i]!=0; i++);
                if(i==numCourses)   return false;
                d[i]=-1;  /*** set d[i]=-1 means delete the node ***/
                for(auto it=matrix[i].begin(); it!=matrix[i].end(); it++) d[*it]--;
            }
            return true;
        }
    };
    

    In fact, I do not really understand the DFS implementations as others' post

    I even can not AC by DFS !

    https://leetcode.com/discuss/42543/18-22-lines-c-bfs-dfs-solutions

    UPDATE

    THe DFS solution is a bit tricky ....

    It is based on the idea of the DFS traversal of the graph ..

    Here is the AC version refered to jianchao.li.fighter....

    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
            vector<bool> onpath(numCourses, false), visited(numCourses, false);
            for (int i = 0; i < numCourses; i++)
                if (!visited[i] && dfs_cycle(graph, i, onpath, visited))
                    return false;
            return true;
        }
    private:
        vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph(numCourses);
            for (auto pre : prerequisites)
                graph[pre.second].insert(pre.first);
            return graph;
        } 
        bool dfs_cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited) {
            if (visited[node]) return false;
            onpath[node] = visited[node] = true; 
            for (int neigh : graph[node])
                if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
                    return true;
            return onpath[node] = false;
        }
    };

  • 0

    Implementation by myself.

    My bug happen when I compute the in-degree-array-of-the-graph and the position to find the in-degree=0 pointer.

       class Solution {
        public:
            bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
                vector<unordered_set<int>> graph(numCourses, unordered_set<int>());
                for(int i=0; i<prerequisites.size(); i++)
                    graph[prerequisites[i].second].insert(prerequisites[i].first);
                vector<int> in_degree(numCourses, 0);
                for(int i=0; i<graph.size(); i++)
                    for(auto it:graph[i])
                        in_degree[it]++;
                        
                int count=0;
                for(int i=0; i<numCourses; i++){
                    int j;
                    for(j=0; j<numCourses; j++) if(in_degree[j]==0)  break;
                    if(j==numCourses)   return false;
                    in_degree[j]=-1;
                    for(auto it : graph[j])   in_degree[it]--;
                }
                return true;
            }
        };

  • 1
    F
    
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<vector<int> > graph(numCourses, vector<int>(0));
            vector<int> visit(numCourses, 0);
            for (auto a : prerequisites) {
                graph[a.second].push_back(a.first);
            }
            for (int i = 0; i < numCourses; ++i) {
                if (!canFinishDFS(graph, visit, i)) return false;
            }
            return true;
        }
        
        bool canFinishDFS(vector<vector<int> > &graph, vector<int> &visit, int i) {
            if (visit[i] == -1) return false;
            if (visit[i] == 1) return true;
            visit[i] = -1;
            for (auto a : graph[i]) {
                if (!canFinishDFS(graph, visit, a)) return false;
            }
            visit[i] = 1;
            return true;
        }
    };

Log in to reply
 

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