python.graphs

By Vitaly Pavlenko, ago, written in Python.
URL http://pastecode.org/index.php/view/29622652
Download Paste or View RawExpand paste to full width of browser | Change Viewing Options
  1. black, grey, white = range(3)
  2.  
  3.  
  4. def dfs_has_cycle(colors, adj_matrix, v):
  5.     colors[v] = grey
  6.  
  7.     res = False
  8.  
  9.     for w, edge in enumerate(adj_matrix[v]):
  10.         if edge == 1:
  11.             if colors[w] == white:
  12.                 res = res or dfs_has_cycle(colors, adj_matrix, w)
  13.             elif colors[w] == grey:
  14.                 res = True
  15.  
  16.     colors[v] = black
  17.     return res
  18.  
  19.  
  20. n = int(input())
  21. adj_matrix = [map(int, input().split()) for i in range(n)]
  22.  
  23. res = False
  24.  
  25. for i in range(n):
  26.     colors = [white for i in range(n)]
  27.     res = res or dfs_has_cycle(colors, adj_matrix, i)
  28.  
  29. if res:
  30.     print(1)
  31. else:
  32.     print(0)

Here you can reply to the paste above

Make Private