SDE GRPAH course schedule

 kanh's algo og topological sort

O(V+E) time Complexity

class Solution { public: vector<int> toposort(vector<vector<int>>&adj,int V){ vector<int>count(V,0); queue<int>q; vector<int>visited; for(int i=0;i<V;i++){ for(int x:adj[i]){ count[x]++; } } for(int i=0;i<V;i++){ if(count[i]==0) q.push(i); } while(!q.empty()){ int x=q.front(); q.pop(); visited.push_back(x); for(int y:adj[x]){ count[y]--; if(count[y]==0)q.push(y); } } return visited; } bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<vector<int>> adj(numCourses); for(auto& e : prerequisites){ adj[e[1]].push_back(e[0]); } vector<int>ans=toposort(adj,numCourses); if(ans.size()==numCourses)return true; return false; } };

my modifie dversion

O(V*V) time complexity

class Solution {

public:

bool canFinish(int n, vector<vector<int>>& prerequisites) {

vector<vector<int>>adj(n);

for(auto e:prerequisites){

adj[e[1]].push_back(e[0]);

}

vector<int>incount(n,0);

for(int i=0;i<n;i++){

for(int x:adj[i])incount[x]++;

}

int n_p_nodes=0;

while(n_p_nodes<=n){

vector<int>toprocess;

for(int i=0;i<n;i++){

if(incount[i]==0){

toprocess.push_back(i);

incount[i]=-1;

}

}

if(toprocess.size()<1)break;

n_p_nodes+=toprocess.size();

for(int x:toprocess){

for(int y:adj[x]){

incount[y]--;

}

}

}

if(n_p_nodes==n)return true;

else return false;

}

};