Simple C++ solution using start and finish time in DFS


#1

int clo = 0;
void DFS(vector adj[],int u, int visit[], int start[], int finish[]){
visit[u]=1;
start[u]=(clo);
(clo)++;
for(int i=0;i<adj[u].size();i++){

    if(visit[adj[u][i]]==0){
        DFS(adj,adj[u][i],visit,start,finish);
    }
}
(clo)++;
finish[u]=(clo);
st.push(u);

}
int Solution::solve(int A, vector &B, vector &C) {
vector adj[A+1];
vector D©;
int i,n=B.size();
if(n<=1)
return 1;
for(i=0;i<n;i++){
adj[B[i]].push_back(C[i]);
}

int start[A+1],finish[A+1],visit[A+1];
for(i=1;i<=A;i++)
    visit[i]=0;
int tim=0;
clo = 0;
sort(C.begin(),C.end());
for(i=0;i<n;i++){
    if(binary_search(C.begin(),C.end(),B[i])==false and visit[B[i]]==0){
        DFS(adj,B[i],visit,start,finish);
    }
}
vector <int> v;
map <int,int> mp;
while(!st.empty())
{
    v.push_back(st.top());
    st.pop();
}
for(i=0;i<v.size();i++)
    mp[v[i]]=i;

for(i=0;i<n;i++){
    if(finish[B[i]]<finish[D[i]])
        return 0;
}
return 1;

}


#2

Only if it was simple.