Mysolution with c++


  • 0
    E

    we can construct a graph, then judge the graph if has a topo sort;

    class Solution {
    public:
        bool topo(int * toposort, int * indegree,int n){
            int cnt = 0;
            queue<int> q;
            int i;
            int count = 0;
            for(i = 0; i < n; i++){
                if(indegree[i] == 0){            
                    q.push(i);
                    count++;
                }
            }
            int cur;
            while(!q.empty()){
                cur = q.front();
                q.pop();
                for(i = 0; i < n; i++){
                    if(toposort[cur*n + i] != 0){
                        indegree[i]--;
                        if(indegree[i] == 0){
                            q.push(i);
                            count++;
                        }
                    } 
                }
            }
            return n == count;
        }
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            int  *arr = (int *)malloc(numCourses*numCourses*sizeof(int));
            int *indegree = (int *)malloc(numCourses * sizeof(int));
            
            memset(indegree,0,numCourses * sizeof(int));
            memset(arr,0,numCourses*numCourses*sizeof(int));
    
            for(int i = 0; i < prerequisites.size(); i++){
                    arr[prerequisites[i].second*numCourses + prerequisites[i].first] = 1;
                    indegree[prerequisites[i].first]++;
            }
            
            bool ret = topo(arr,indegree,numCourses);
            free(arr);
            free(indegree);
            return ret;
        }
    };
    
    
    

Log in to reply
 

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