Another simple approach to solve above question by using disjoint set data structure to detect cycle


#1

`int find(int a,vector&s)
{
if(s[a]==-1)
return a;
else
return find(s[a],s);
}
void unionag(int x,int y,vector&s)
{
int pa=find(x,s);
int pb=find(y,s);
s[pb]=pa;
}
int Solution::solve(int A, vector &B, vector &C)
{
if(B.size()==0||C.size()==0)
return 1;
else
{
vectorset(A+1,-1);
for(int i=0;i<B.size();i++)
{
if(find(B[i],set)!=find(C[i],set))
unionag(B[i],C[i],set);
else
return 0;
}

 }
 return 1;

}`es here.


#2

Your approach is wrong as your algo works for undirected graphs, Look at the question carefully,the question is about cycle detection in directed graph.


#3

Actually it will work for undirected also and same approach I used in the question in course schedule 2 leetcode you can check and please let me know why it will not work for directed one because we are using the concept of disjoint sets actually it’s for directed only what I think


#4

union of 1->2 can’t be done, because there is no path from 2 to 1 ,but in undirected graph 1-2, union is possible