Нужно определить есть ли цикл в неориентированном графе и вывести все вершины этого цикла. Граф вводится количеством вершин и матрицей смежности. Вот что написал:
n = int(input())
matr = []
for _ in range(n):
streng = list(map(int, input().split()))
matr.append(streng)
lister = [[] for i in range(n)]
for i in range(n):
for j in range(n):
if matr[i][j] == 1:
lister[i].append(j)
visited = set()
def dfs(lister, visited, curr, prev=-1):
visited.add(curr)
checkers = False
for now in lister[curr]:
if prev != now:
if now in visited:
return True
if dfs(lister, visited, now, curr):
return True
visited.remove(curr)
return checkers
for i in range(n):
ret = dfs(lister, visited, i)
if ret:
break
visited.clear()
if ret:
print("YES")
print(len(visited))
visited = map(lambda x: x + 1, visited)
print(*visited)
else:
print("NO")
Есть/нет цикл оно определяет правильно, но вот вершины в цикле нет. Например, если будет граф с соединенными по кругу вершинами, но при этом будет вершина отдельная, соединяющаяся с одной из вершин круга, то она войдет в этот цикл, хотя не должна.
4
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
Таким вводом, например, вторая вершина в цикл не входит, но выведет 1 2 3 4, т. е. все вершины. Что нужно добавить?
Немного подправил. Теперь оно все тупиковые ветки будет удалять, но если начать обход с такой ветки, то она останется.