Topological sort solution in c++


#1

vector<vector> g;
vector vis, act;
int isPossible;

void dfs(int v){
vis[v] = true;
act[v] = true;
for(int u : g[v]){
if(act[u] && v^u) isPossible = 0;
if(!vis[u]) dfs(u);
}
act[v] = false;
}

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

// Construct graph
g = vector<vector<int>> (A);
for(int i=0;i<B.size();i++){
    g[B[i]-1].push_back(C[i]-1);
}

// initalize arrays
vis = vector<bool> (A, false);
act = vector<bool> (A, false);
isPossible = 1;

// DFS 
for(int i=0;i<A;i++){
    if(!vis[i]) dfs(i);
}

return isPossible;

}