那作业

Josefine 整个夏天都在决定她想在算法大学学习哪些课程。一门课程需要一个学期才能完成（作为超级学生，她总是能成功）。有些课程依赖于其他课程，因此不允许在同一学期修读这些课程。如果课程 i 依赖于课程 j，则 Josefine 必须在课程 j 之前的学期学习课程 i。她希望在尽可能少的学期内完成学业。

给定 Josefine 想要学习的 N 门课程（从 1 到 N 编号）以及它们各自依赖的课程，计算 Josefine 完成学业所需的最少学期数。（同样，她是一名超级学生，所以她每学期可以选修无限数量的课程）。

你可以假设 Josefine 选择的课程没有循环依赖。

输入格式

Line 1: The integers N and M, where N is the number of courses and M is the total number of dependencies.
Line 2..M+1: Two integers X and Y meaning the course X depends on the course Y (ie. course Y must have been completed before course X)

输出格式

Line 1: The fewest number of semesters Josefine needs to use.

我当前的代码

NM = input()
NM = NM.split(" ")
N = int(NM[0])
M = int(NM[1])

remCourses = []
courseRes = {}
for i in range(1,N+1):
    courseRes[str(i)] = list()
    remCourses.append(str(i))

for i in range(0,M):
    res = input()
    res = res.split(" ")
    courseRes[str(res[0])].append(str(res[1]))

semCount = 0
while len(remCourses) > 0:
    newCourses = []
    for key in courseRes:
        if len(courseRes[key]) == 0:
            newCourses.append(key)


    for l in range(1,N+1):
        for course in newCourses:
            if course in courseRes[str(l)]:
                courseRes[str(l)].remove(course)

    for course in newCourses:
        if course in remCourses:
            remCourses.remove(course)

    semCount += 1

print(semCount)

我的问题是代码速度不够快，无法获得所需的分数。非常感谢 som 的帮助。

提前致谢：）

标签： python

解决方案

通过使用集合操作，您可以更快地找到解决方案。

首先假设我们有以下依赖：

deps = [(11, 2), (11, 9), (8, 9), (11, 10), (3, 10),
        (5, 11), (7, 11), (7, 8), (3, 8)]

形成下图：

找到她在第一学期需要修读的课程：

semesters = []
sources = {start for start, end in deps}
sinks   = {end for start, end in deps}
semester = sources - sinks
semesters.append(semester)

即找到图中的所有根（没有任何传入箭头的节点）。

然后删除根：

deps = [(start, end) for start, end in deps if start not in semester]

并重复...

semesters = []
while deps:
    sources = {start for start, end in deps}
    sinks   = {end for start, end in deps}
    semester = sources - sinks
    semesters.append(semester)
    deps = [(start, end) for start, end in deps if start not in semester]

print("semesters needed:", 1 + len(semesters))

我们需要加 1，因为最后一次删除根删除了 2 级节点。

我们可以使用该timeit模块比较两个版本（我已将您的代码放在一个函数中并修复了几个错误）：

def semestercount():
    deps = [(11, 2), (11, 9), (8, 9), (11, 10), (3, 10),
            (5, 11), (7, 11), (7, 8), (3, 8)]
    count = 0
    while deps:
        sources = {start for start, end in deps}
        sinks   = {end for start, end in deps}
        semester = sources - sinks
        count += 1
        deps = [(start, end) for start, end in deps if start not in semester]
    return count + 1


def op_code():
    NM = [(11, 2), (11, 9), (8, 9), (11, 10), (3, 10),
          (5, 11), (7, 11), (7, 8), (3, 8)]
    nodes = list(set(sum(NM, ())))
    N = len(nodes)
    M = len(NM)
    remCourses = []
    courseRes = {}
    for i in range(N):
        courseRes[nodes[i]] = list()
        remCourses.append(nodes[i])

    for i in range(0,M):
        res = NM[i]
        courseRes[res[0]].append(res[1])

    semCount = 0
    while len(remCourses) > 0:
        newCourses = []
        for key in courseRes:
            if len(courseRes[key]) == 0:
                newCourses.append(key)


        for l in range(N):
            for course in newCourses:
                if course in courseRes[nodes[l]]:
                    courseRes[nodes[l]].remove(course)

        for course in newCourses:
            if course in remCourses:
                remCourses.remove(course)

        semCount += 1
    return semCount


import timeit
print timeit.timeit("semestercount()", "from __main__ import semestercount")
print timeit.timeit("op_code()", "from __main__ import op_code")

在我的电脑上打印：

5.85758427398
42.8849096743

所以要快一点:-)

python - 优化算法

问题描述

那作业

我当前的代码

解决方案

推荐阅读