Mysolution with c++

• 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;
}
};

``````

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