C++, My solution , using Topological sort, easy to understand :)


  • 1
    C
     - Actually, the problem is AOV net.
     - Firstly, we build a graph to describe the problem using adjacency list.
     - Then, we sort the graph into topological sorting.
     - If you don't understand, you can review the Graph data structure about 
       topological sort,that's good for programming! :)
        
     /**
      ** author: cxq
      ** weibo: http://weibo.com/chenxq1992
      **/   
    class Solution {
    public:
        typedef struct VNode {
            int indgree;
            vector<int> arcs;
            VNode(int x=0):indgree(x){}
        }VNode;
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            vector<VNode> graph;
            for (int i = 0; i < numCourses; ++i) {
                VNode tmp;
                graph.push_back(tmp);
            }
            const int m = prerequisites.size();
            for (int i = 0; i < m; ++i) {
                int v = prerequisites[i][0];
                int u = prerequisites[i][1];
                if (find(graph[v].arcs.begin(), graph[v].arcs.end(), u) == graph[v].arcs.end()) {
                    ++graph[u].indgree;
                    graph[v].arcs.push_back(u);    
                }
            }
            stack<int> s;
            for (int i = 0; i < numCourses; ++i)
                if (graph[i].indgree==0) s.push(i);
            int count = 0;
            while (!s.empty()) {
                int i = s.top();s.pop();
                ++count;
                for (auto j = graph[i].arcs.begin(); j != graph[i].arcs.end(); ++j) {
                    if (--graph[*j].indgree == 0) s.push(*j);
                }
            }
            return count < numCourses ? false : true;
        }
    };

Log in to reply
 

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