Simple C++ solution using topological sort


#1

`
int Solution::solve(int A, vector &B, vector &C)
{

vector<vector<int>> dependents;
for(int i = 0; i < A; i++)
{
    vector<int> temp;
    dependents.push_back(temp);
}
int indegree[A] = {0};
for(int i = 0; i < B.size(); i++)
{
    dependents[B[i] - 1].push_back(C[i]);
    indegree[C[i] - 1]++;
}
vector<int> zeroes;
int req = 0, x;
for(int i = 0; i < A; i++)
    if(indegree[i] == 0) zeroes.push_back(i + 1);
while(zeroes.size() > 0)
{
    req++;
    x = zeroes.back();
    zeroes.pop_back();
    for(int i = 0; i < dependents[x - 1].size(); i++)
    {
        indegree[dependents[x - 1][i] - 1]--;
        if(indegree[dependents[x - 1][i] - 1] == 0)
            zeroes.push_back(dependents[x - 1][i]);
    }
}
if(req == A) return 1;
else return 0;

}
`