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 isCyclic(int V, vector<vector<int>> &edges) {
// code here
vector<vector<int>> adj(V);
for(auto& e : edges){
adj[e[0]].push_back(e[1]);
}
vector<int>ans=toposort(adj,V);
if(ans.size()==adj.size()) return false;
else return true;
}
};
No comments:
Post a Comment