DFS Solution. Cpp


#1
#define pb push_back
#define ff first
#define ss second
vector<int> graph[60005];
vector<int> allV;
vector<int> vis;
vector<int> still;
bool flag = true;
void dfs(int source){
    if(vis[source])
        return;
    if(!flag)
        return;
    vis[source] = 1;
    still[source] = 1;
    for(int i = 0; i<graph[source].size();i++){
        int node = graph[source][i];
        if(still[node]==1){
            flag = false;
            return;
        }
        if(vis[node])
            continue;
        dfs(node);
    }
    still[source] = 0;
}
int Solution::solve(int A, vector<int> &B, vector<int> &C) {
    allV.resize(A+1);
    vis.resize(A+1);
    still.resize(A+1);
    for(int i = 0; i<=A; i++){
        allV[i] = 1;
        vis[i] = 0;
        still[i] = 0;
        graph[i].clear();
    }
    for(int i = 0; i<B.size(); i++){
        int prereq = B[i];
        int with = C[i];
        allV[with] = 0;
        graph[prereq].pb(with);
    }
    flag = true;
    for(int i = 1; i<=A; i++){
        if(allV[i]==1 && vis[i]==0){
            dfs(i);
            if(!flag)
                return 0;
        }
    }
    int cnt = 0;
    
    for(int i = 1; i<=A; i++){
        cnt+=vis[i];
    }
    return cnt==A?1:0;
}