python.graphs

Go Back — Change Paste Viewing Options

black, grey, white = range(3)
 
 
def dfs_has_cycle(colors, adj_matrix, v):
    colors[v] = grey
 
    res = False
 
    for w, edge in enumerate(adj_matrix[v]):
        if edge == 1:
            if colors[w] == white:
                res = res or dfs_has_cycle(colors, adj_matrix, w)
            elif colors[w] == grey:
                res = True
 
    colors[v] = black
    return res
 
 
n = int(input())
adj_matrix = [map(int, input().split()) for i in range(n)]
 
res = False
 
for i in range(n):
    colors = [white for i in range(n)]
    res = res or dfs_has_cycle(colors, adj_matrix, i)
 
if res:
    print(1)
else:
    print(0)			

Go Back