Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- 0---------------->not visited
- 1---------------->processing
- 2---------------->processes
- """
- class Solution:
- def canFinish(self, n: int, p: List[List[int]]) -> bool:
- def iscycle(src):
- if vis[src]==1:#you are coming back to the ancestor so this shows cycle
- return True
- vis[src]=1# now we are processing
- for node in adj[src]:
- if vis[node]!=2:#if vertex not processed call dfs on that vertex
- if iscycle(node):
- return True
- vis[src]=2
- return False
- adj=[[] for i in range(n)]
- for i in p:
- adj[i[0]].append(i[1])
- vis=[0 for i in range(n)]
- for i in range(n):
- if vis[i]==0:
- if iscycle(i):
- return False
- return True
Add Comment
Please, Sign In to add comment