DFS without coloring


#1

The same priciple though…

bool dfs(const vector<vector<int>>& g, unordered_set<int>* unvisited, unordered_set<int>* visited, int s){
    if(visited->find(s) != visited->end()) return true;
    
    visited->insert(s);
    unvisited->remove(s);
    
    for(auto adj: g[s]){
        bool circle = dfs(g, unvisited, visited, adj);
        if(circle) return true;
    }
    return false;
}

int Solution::solve(int N, vector<int> &B, vector<int> &C) {
    vector<vector<int>> g(N+1);
    unordered_set<int> unvisited;
    for(int i=1; i<=N; ++i){
        unvisited.insert(i);
        g[B[i]].push_back(C[i]);
    }
    
    while(!unvisited.empty()){
        unordered_set<int> visited();
        bool circle = dfs(g, &unvisited, &visited, *unvisited.begin());
        if(circle) return false;
    }
    
    return true;
}