Графы, обход в глубину. Задача "Построение"

Рейтинг: -1Ответов: 2Опубликовано: 01.08.2023

Код прошел не все тесты(, скажите, пожалуйста, в чем ошибка

https://informatics.msk.ru/mod/statements/view.php?id=256&chapterid=166#1 - задача

Группа солдат-новобранцев прибыла в армейскую часть N666. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо.

Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине.

После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен.

Входные данные Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны.

Выходные данные В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений.

Потом в дфс делаю топологическую сортировку

def dfs(v):
    global u
    visited.add(v)
    new_visited.add(v)
    for i in graph[v]:
        if (i not in visited):
            dfs(i)
        elif (i in new_visited):
            u=0
    res.append(v)
    

global u
u = 1
global res
res = []
n, m = map(int, input().split())
visited = set()
graph = []
ans = []
for i in range(n):
    graph.append([])
for i in range(m):
    p, v = map(int, input().split())
    graph[p-1].append(v-1)
    
visited = set()
new_visited = set()
for i in range(n):
    if i not in visited:
        new_visited = set()
        dfs(i)
        ans = reversed(res)
if (u):
    print("Yes")
    for i in ans:
        print(i+1, end = " ")
else:
    print("No")
python графы
Источник: Stack Overflow на русском

Ответы

▲ 0Принят

Строим направленный граф, в котором узлы запоминают кто выше их. У вас наоборот. Это нужно чтобы после сортировки не нужно было переворачивать результат.

Топологическая сортировка совмещена с поиском циклов. В отличие от работы с ненаправленными графами, где было множество visited и вершина parent, тут будут два множества: visited и traversed. Вершины графа сперва попадают в traversed, затем перекладываются в visited.

NB Иногда при описании обходов используют не множества а "цвета" для вершин: "белая" - ещё не обрабатывалась, "серая" - в процессе обхода (traversed), "черная" - обработана раньше (visited).

Сама сортировка - рекурсивный поиск в глубину (процедура traverse). Цепочка вершин от корня до текущей хранится в множестве traversed. Если в процессе поиска мы попали в вершину уже из этого множества, то в графе есть цикл. Когда обработка вершины в поиске завершена, она удаляется из traversed и помещается в visited.

Вершины которые попали в visited также накапливаются в списке result, который обладает следующим свойством: вершина попадает в него только после всех своих потомков (детей, внуков и т.п.). Следовательно, вершина окажется в списке только тогда когда все более рослые вершины уже там.

def toposort(graph):
    n = len(graph)
    visited = [False] * n
    traversed = [False] * n
    result = []

    def traverse(i):
        if traversed[i]:
            return False
        traversed[i] = True
        for j in graph[i]:
            if not visited[j] and not traverse(j):
                return False
        traversed[i] = False
        visited[i] = True
        result.append(i)
        return True

    for i in range(n):
        if not visited[i] and not traverse(i):
            return None
    return result


def main():
    n, m = map(int, input().split())
    graph = tuple([] for _ in range(n))
    for _ in range(m):
        i, j = map(lambda w: int(w) - 1, input().split())
        graph[j].append(i)
        
    result = toposort(graph)
    if result is None:
        print('No')
    else:
        print('Yes')
        print(*(i + 1 for i in result))


main()
▲ 1

У меня сначала были просто затупы, типа, цикл найдется только там, где есть первая вершина Потом я поняла, что ищу цикл, как в неориентированном графе, а у меня ориентированный немного запуталась с массивом color: if (color[child] == 0): color[child] = 1 Эта строчка была важной...

И без отдельной проверки на цикл я запуталась, так что разнесла на 2 отдельные функции

def check(child):
    global u
    if (color[child] == 0):
        color[child] = 1
    visited.add(child)
    for v in graph[child]:
        if (v not in visited):
            check(v)
        elif (color[v] == 1):
            u = 1
    color[child] = 2


def dfs(v):
    visited.add(v)
    for i in graph[v]:
        if (i not in visited):
            dfs(i)
    res.append(v)
    

global u
u = 0
global res
res = []
n, m = map(int, input().split())
visited = set()
graph = []
for i in range(n):
    graph.append([])
for i in range(m):
    p, v = map(int, input().split())
    graph[p-1].append(v-1)
color = [0] * n
for i in range(n):
    if i not in visited:
        check(i)
#0 - белый
#1 = серый
#2 - черный
#print(u)
ans = []
if (u==1):
    print("No")
else:
    visited = set()
    for i in range(n):
        if i not in visited:
            #visited = set()
            dfs(i)
            ans = reversed(res)
    print("Yes")
    for i in ans:
        print(i+1, end = " ")