Помогите. Задача на хранение и обход графов

Question

Нужно сдать решение до 19 мая на stepik.

Вы наметили num курсов для обучения, которые пронумеровали от 0 до num-1. Некоторые курсы имеют требования для их прохождения. Например, курс под номером 0 требует прохождения курса под номером 1. Такое отношение обозначается парой: [0,1].

Вам дано общее количество курсов и список пар-требований. Сможете ли вы пройти все курсы?

ПРИМЕРЫ:

Sample Input 1:

2 [[1,0]]

Sample Output 1:

True

Sample Input 2:

2 [[1,0],[0,1]]

Sample Output 2:

False

Я попробовал такое решение. Оно работает с текущими примерами, но на 3-ем тесте ломается. И stepik не показывает какие входные данные... может кто заметит, что не так в коде?

def canFinish(self, num: int, courses: list):
    co = []
    completed = [False] * num
    yes = 0

    for idx in range(num-1):
        if courses[idx] != None:
            for case in courses:
                nado = case[1]
                foWhat = case[0]
                curId = courses.index(case)
                if curId == nado:
                    completed[curId] = True
                #print(case)
                #print(completed)
    for i in completed:
        if i: yes += 1
    #print(yes, num-1)
    if yes == num-1: return True
    else: return False

Answer 1

Это, скорее всего, не самый оптимальный вариант, но он рабочий

def coursePass(count, deps = []):
    #множество с номерами уже пройденных курсов
    passed = set()

    while len(passed) != count:
        #множество курсов, которые мы сейчас можем пройти(по умолчанию все, которые не в множестве passed)
        canPass = {i for i in range(0, count) if i not in passed}

        for dep in deps:
            #убираем с курсов, которые мы можем пройти те, которые
            #зависят от непройденных курсов

            if dep[1] not in passed:
                canPass.remove(dep[0])

        # если количество курсов, которые мы можем пройти не равно нулю, то
        #добавляем их, иначе возвращаем False

        if len(canPass):
            passed |= canPass
        else:
            return False

    # количество пройденных курсов равно общему количеству курсов, значит
    #возвращаем True
    return True

Answer 2

Алгоритм

Используя список courses создаём словарь с зависимостями первого уровня для каждого курса. Для списка [[1, 2], [2, 3], [3, 4]] словарь будет выглядеть так:
```
{
    1 : {2, 3, 4},
    2 : {3, 4},
    3 : {4}
}    
```
Далее перебираем этот словарь, поочерёдно проверяя для каждого курса всю цепочку его зависимостей. False возвращается в двух случаях:
- происходит попытка повторно войти в один и тот же курс, значит в цепочке есть цикл вида [[0, 1], [1, 0]], следовательно курсы зависят друг от друга.
- курс зависит от курса не попадающего в допустимый диапазон, например от курса 10, когда их всего 5.

Решение

class Solution:
    def canFinish(self, num: int, courses: list) -> bool:
        dct_of_dependencies = {k : set() for k in range(num)}

        for target_course, dependency in courses:
            dct_of_dependencies[target_course].add(dependency)

        for target_course, dependencies_to_check in dct_of_dependencies.items():
            visited = {target_course}
            while dependencies_to_check:
                nxt = dependencies_to_check.pop()
                # Проверка 'nxt >= num' нужна, так как в некоторых тестах есть курсы, 
                # которые зависят от курсов вне диапазона num.
                # Иначе решение не проходит
                if nxt in visited or nxt >= num:
                    return False

                if dct_of_dependencies[nxt]:
                    dependencies_to_check.update(dct_of_dependencies[nxt])
                    visited.add(nxt)

        return True

БЛОГ НА HUSL

Помогите. Задача на хранение и обход графов

Ответы (2 шт):