 # 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;
}
``````