0

Нужно определить есть ли цикл в неориентированном графе и вывести все вершины этого цикла. Граф вводится количеством вершин и матрицей смежности. Вот что написал:

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, т. е. все вершины. Что нужно добавить?

Немного подправил. Теперь оно все тупиковые ветки будет удалять, но если начать обход с такой ветки, то она останется.

2

1 ответ 1

0

Сделал сам

from collections import deque

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()
result = deque()


def dfs(lister, visited, curr, prev=-1):
    visited.add(curr)
    result.append(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)
    result.pop()
    return checkers


for i in range(n):
    ret = dfs(lister, visited, i)
    if ret:
        break
    visited.clear()

if ret:
    while result[0] not in lister[result[-1]]:
        result.popleft()
    print("YES")
    print(len(result))
    visited = map(lambda x: x + 1, result)
    print(*visited)
else:
    print("NO")

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.