Iam_Sandeep

check cycle directed graph : graph coloring method

Jun 6th, 2021 (edited)
431
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.92 KB | None | 0 0
  1. """
  2. 0---------------->not visited
  3. 1---------------->processing
  4. 2---------------->processes
  5. """
  6.  
  7. class Solution:
  8.     def canFinish(self, n: int, p: List[List[int]]) -> bool:
  9.         def iscycle(src):
  10.             if vis[src]==1:#you are coming back to the ancestor so this shows cycle
  11.                 return True
  12.             vis[src]=1# now we are processing
  13.             for node in adj[src]:
  14.                 if vis[node]!=2:#if vertex not processed call dfs on that vertex
  15.                     if iscycle(node):
  16.                         return True
  17.             vis[src]=2
  18.             return False
  19.         adj=[[] for i in range(n)]
  20.         for i in p:
  21.             adj[i[0]].append(i[1])
  22.         vis=[0 for i in range(n)]
  23.         for i in range(n):
  24.             if vis[i]==0:
  25.                 if iscycle(i):
  26.                     return False
  27.         return True
  28.            
  29.                
  30.                
  31.        
Add Comment
Please, Sign In to add comment