위상 정렬.

잘 설명된 블로그 : http://jinsolkim.kr/220069891025

먼저 선행되는 작업들 이후에 어떤 작업이 가능하다고 할 경우에 최소한의 시간을 구하는 그런 알고리즘.

아래는 코드. 입력값은 아래처럼 넣어보자. 4 4는 점 4개에, 간선이 4개라는 소리이고, 1 2는 노드 1에서 노드 2로가는 간선 하나가 있다는 소리이다. 나머지도 그런 소리이다.

%입력이 다양하게 주어질 경우 그 중에서 가능한 한 경우만 출력한다. 다른 경우를 출력하려면 따로 돌려야 될듯 싶다.

4 4  

1 2

1 3

2 4

3 4

# -*- encoding: cp949 -*-
import Queue
v,e = map(int,raw_input().split()) #노드,간선수 입력받음
adj = [[] for i in range(v+1)] #한 노드에서 몇개의 노드로 퍼져나가는지 간선을 전부 저장한 리스트
indegree = [0 for i in range(v+1)] #해당 노드가 시작되려면 몇개의 간선이 들어와야되는지 저장해놓은 리스트
for i in range(e): #간선 수만큼
    a,b = map(int,raw_input().split()) #가는 경로를 입력받아서
    adj[a].append(b) #각각 간선을 저장한다.
    indegree[b] += 1 #간선이 하나 들어왔으므로 해당 노드의 간선 1 증가.

print adj #확인용
print indegree #확인용
pq = Queue.Queue()
for i in range(1,v+1): #큐를 만들어서 시작점, 즉 해당 노드가 시작되려면 간선이 없어도 되는, 0개인 것들을 큐에 저장해놓는다.
    if indegree[i]==0:
        pq.put(i)

while not pq.empty():
    here = pq.get() #큐에서 하나 꺼내와서
    print 'order =',here #순서 보기용으로 출력
    for i in range(len(adj[here])): #꺼내온 노드에서 '퍼져나가는' 간선들을 정리한다.
        there = adj[here][i] #here노드에서 한번에 갈수 있는 노드이다.
        indegree[there] -= 1 #갔다고 생각하고 해당 노드가 시작되려면 필요한 간선을 1개 줄인다.
        if indegree[there]==0: #간선이 0개가되면 큐에 넣고 동일한 작업을 반복한다.
            pq.put(there)

print