minimario

Untitled

Jun 19th, 2015
320
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.03 KB | None | 0 0
  1. global cycle, cycle_begin, cycle_end
  2. cycle = -1
  3. cycle_begin = 0
  4. cycle_end = 0
  5.  
  6. def dfs(s):
  7.     global cycle, cycle_begin, cycle_end
  8.     visited[s] = 1
  9.  
  10.     for i in range(len(g[s])):
  11.         if visited[g[s][i]] == 0:
  12.             parent[g[s][i]] = s
  13.             dfs(g[s][i])
  14.         elif visited[g[s][i]] == 1:
  15.             cycle = 1
  16.             cycle_begin = g[s][i]
  17.             cycle_end = s
  18.            
  19.  
  20.     visited[s] = 2
  21.    
  22.            
  23.    
  24. n, m = map(int, input().split(' '))
  25.  
  26. g = {}
  27. for i in range(1, n+1):
  28.     g[i] = []
  29.  
  30. for i in range(m):
  31.     a, b = map(int, input().split(' '))
  32.     g[a].append(b)
  33.  
  34. parent = [0] * (n+1)
  35. visited = [0] * (n+1)
  36. path = []
  37.  
  38. for i in range(1, n):
  39.     if cycle == 1:
  40.         break
  41.     if visited[i] == 0:
  42.         dfs(i)
  43. if cycle == 1:
  44.     print("YES")
  45.     a = []
  46.     while cycle_end != cycle_begin:
  47.         a.append(str(cycle_end))
  48.         cycle_end = parent[cycle_end]
  49.     a.append(str(cycle_begin))
  50.     a.reverse()
  51.     print(' '.join(a))
  52.  
  53. else:
  54.     print("NO")
Advertisement
Add Comment
Please, Sign In to add comment