トポロジーソートの適用---leetcode 207カリキュラム
1096 ワード
トポロジーソートは無ループ図への応用であり,オフセット定義からトポロジー秩序を得る動作をトポロジーソートと呼び,トポロジー秩序は全シーケンスである.
トポロジのソート方法:
1.図面に入力度0(つまり、前駆者なし)のノード出力を選択する
2.図からノードとそれを起点とする依存関係を削除する
3.すべてのノードが出力されるか、または現在前駆者のないノードが存在しないまで(この場合、ループが存在することを示す).
コードの出典http://www.zhufangxing.com/2015/05/01/leetcode-ICourse%20Schedule/勉強して
トポロジのソート方法:
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)