Topological Sort /Cycle Detection / Kahn's Algorithm


#1

int Solution::solve(int A, vector &B, vector &C) {
vector v[A+1];
vector in(A+1,0);
for(int i=0;i<B.size();i++)
{
v[B[i]].push_back(C[i]);
in[C[i]]++;
}

queue<int> q;
for(int i=1;i<=A;i++)
    if(in[i]==0)q.push(i);

vector<int> vis(A+1,0),top;
while(!q.empty())
{
    auto p=q.front();
    q.pop();
    top.push_back(p);
    for(auto x:v[p])
    {
        in[x]--;
        if(in[x]==0)q.push(x);
    }
}
return top.size()==A;

}