Untitled

graph = [[1], [2, 3], [1, 4, 5], [1, 6], [2], [2], [3, 7, 8], [1, 6], [6]]


# Використовує DFS для пошуку циклу в графі (19-21)
def dfs(graph, start_vertex):
    visited = [False for x in graph]
    distances = [0 for x in graph]
    vertex_to_visit_queue = [start_vertex]

    while vertex_to_visit_queue:
        current_vertex = vertex_to_visit_queue.pop()
        for neighbour in graph[current_vertex]:
            if not visited[neighbour]:
                vertex_to_visit_queue.append(neighbour)
                distances[neighbour] = distances[current_vertex] + 1
            # Перевірка чи вертекси не є сусідами, бо
            # якщо граф не направлений і ти вернувся від сина до
            # батька, то це не цикл
            elif current_vertex not in graph[neighbour]:
                print('Loop found')
                return
        visited[current_vertex] = True

    return distances


print(dfs(graph, 0))