Поиск цикла

@mulli_ · Регистрация: 02.04.2023

Студворк — интернет-сервис помощи студентам

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

Формат ввода
В первой строке дано одно число n — количество вершин в графе ( 1 ≤ n ≤ 500 ). Далее в n строках задан сам граф матрицей смежности.

Формат вывода
Если в иcходном графе нет цикла, то выведите «NO». Иначе, в первой строке выведите «YES», во второй строке выведите число k — количество вершин в цикле, а в третьей строке выведите k различных чисел — номера вершин, которые принадлежат циклу в порядке обхода (обход можно начинать с любой вершины цикла). Если циклов несколько, то выведите любой.

Ввод
3
0 1 1
1 0 1
1 1 0

Вывод
YES
3
3 2 1

Выдает ошибку в коде:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def dfs(v, g, used, p):
    used[v] = 1
    for i in g[v]:
        if (used[i] == 0):
            p[i] = v
            res = dfs(i, g, used, p)
            if res != None:
                return res
        elif used[i] == 1 and i != p[v]:
            return v, i
 
used = [0] * n
p = [-1] * n
cycle = []
 
for i in range(n):
    if used[i] == 0:
        val = dfs(i, g, used, p)
        if val != None:
            v, i = val
        while v != i:
            cycle.append(v)
            v = p[v]
        cycle.append(v)
        break
 
if len(cycle) > 0:
    print('YES')
    print(len(cycle))
    print(*cycle)
else:
    print('NO')

@Informatikc · 02.04.2023, 21:57

mulli_, попробуй возможно
код не полный, так как отсутствуют объявления переменных n и g, а также пропущены отступы для вложенных блоков и операторы условия. Для решения задачи также нужно обработать входные данные и построить из них граф, а затем вызвать функцию dfs для каждой непосещенной вершины. Вот полный код (если ни где не ошибся):

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
n = int(input())
g = []
for i in range(n):
    row = list(map(int, input().split()))
    g.append([j for j in range(n) if row[j] == 1])
 
def dfs(v, g, used, p):
    used[v] = 1
    for i in g[v]:
        if used[i] == 0:
            p[i] = v
            res = dfs(i, g, used, p)
            if res != None:
                return res
        elif used[i] == 1 and i != p[v]:
            return v, i
 
used = [0] * n
p = [-1] * n
 
for i in range(n):
    if used[i] == 0:
        val = dfs(i, g, used, p)
        if val != None:
            v, i = val
            cycle = [v]
            while v != i:
                v = p[v]
                cycle.append(v)
            print('YES')
            print(len(cycle))
            print(*cycle[::-1])
            break
 
if 'cycle' not in locals():
    print('NO')

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .