FilesExpand file tree

 main

/

graph1.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (48 loc) · 1.05 KB

 main

/

graph1.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (48 loc) · 1.05 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

//Finding cycle in a directed graph

//dfs till you meet a visited node.

//Also maintain a inrecursion array.

#define pb push_back

int find(int src,vector<vector<int>>&v,int *vis,int *st)

{

vis[src]=1; st[src]=1;

for(int i=0;i<v[src].size();i++)

{

int tar=v[src][i];

if(vis[tar]==0)

{

if(find(tar,v,vis,st))

{

return 1;

}

}

else

{

if(st[tar]==1)

return 1;

}

}

st[src]=0;

return 0;

}

int Solution::solve(int A, vector<vector<int> > &B)

{

vector<vector<int>>dp(A);

if(A<=2)

return 0;

int n=B.size();

for(int i=0;i<n;i++)

{

dp[B[i][0]-1].pb(B[i][1]-1);

}

int vis[A]={0};

int st[A]={0};

for(int i=1;i<=A;i++)

{

if(vis[i]==0)

{

if(find(i,dp,vis,st))

return 1;

}

}

return 0;

}