トポロジーソートの適用---leetcode 207カリキュラム


トポロジーソートは無ループ図への応用であり,オフセット定義からトポロジー秩序を得る動作をトポロジーソートと呼び,トポロジー秩序は全シーケンスである.
トポロジのソート方法:
1.図面に入力度0(つまり、前駆者なし)のノード出力を選択する
2.図からノードとそれを起点とする依存関係を削除する
3.すべてのノードが出力されるか、または現在前駆者のないノードが存在しないまで(この場合、ループが存在することを示す).
コードの出典http://www.zhufangxing.com/2015/05/01/leetcode-ICourse%20Schedule/勉強して
 
def canFinish(numCourses, prerequisites):
    if numCourses < 2 or len(prerequisites) < 2:
        print('True')
        return True
    while True:
        count = 0
        mark = [True] * numCourses ###true     0          
        for pre in prerequisites:
            mark[pre[0]] = False
        for pre in prerequisites:
            if mark[pre[1]]:
                count += 1
                prerequisites.remove(pre)
        if prerequisites == []:
            print('True')
            return True
        elif count == 0:
            print('false')
            return False



numCourses, prerequisites = 4, [[1,0],[2,0],[3,1],[3,2]]
#numCourses, prerequisites = 2, [[1,0],[0,1]]
canFinish(numCourses,prerequisites)