Lang: C++; Complexity[Time,Space]`: [O(n+m), O(n*m)]


#1

Where in title

  • n = Total number of nodes/vertices in graph
  • m = Total number of edges in graph

Idea: If a cycle exists return 0 else 1. Here if while processing a node i.e., when its state is ACTIVE if another node is encountered with state ACTIVE then a cycle is present.

#define UNSEEN 0
#define ACTIVE 1
#define SEEN 2
bool dfs(int node, vector<vector<int>>&graph, vector<int>&state)
{
    if(state[node] == SEEN)
        return false;
    else if(state[node] == ACTIVE)
        return true;
    
    bool hasCycle=false;
    state[node] = ACTIVE;
    for(auto v: graph[node])
        hasCycle = hasCycle || dfs(v,graph,state);
    state[node] = SEEN;
    return hasCycle;
}
int Solution::solve(int A, vector<int> &B, vector<int> &C) 
{
    vector<vector<int>> graph(A+1,vector<int>());
    for(int i=0; i<B.size(); i++)
    {
        if(B[i] == C[i])
            return 0;
        graph[B[i]].push_back(C[i]);
    }
    vector<int> state(A+1, UNSEEN);
    for(int i=1; i<=A; i++)
    {
        bool hasCycle=dfs(i, graph, state);
        if(hasCycle) return 0;
    }
    return 1;
}