#1766: 문제집

https://www.acmicpc.net/problem/1766

이 문제를 처음 보고 드는 생각.

어 이거 위상정렬 문제 아니냐?

무엇을 하기 전에 다른 걸 먼저 해야 한다 <- 위상정렬 문제들의 특징

대충 인풋 확인한 후 N = 32000?
그럼 위상정렬용 배열을 만들 수 있겠군 싶었음.

그렇다면 작은 수부터 푸는 건 어떻게 해결하나?

그냥 1부터 무지성으로 시도하고, 1 풀기전에 풀어야하는 문제들을 차근차근 풀어나가면 되지 않을까?

반례:

1을 풀기 위해 2를 풀어야 하고, 2를 풀기 위해 3과 4를 풀어야 하고, 3을 풀기 위해 4를 …

이러면 결국 하나하나 다 스캐닝하는 거라 시간복잡도 올라감…

아, 그렇다면 그냥 인접 정점의 갯수가 0인 놈들 중 작은 놈들부터 시작하면 되겠네?

ㄴㄴ 그놈들을 풀면서 새로운 놈들이 계속 추가됨.

이걸 어떻게 해결하나? 가만히 생각해보니

작은 놈들이 도중에 계속 추가되어서 다시 재정렬해야 한다 <- 우선순위큐 사용하면 해결

아 적절히 위상정렬과 우선순위큐를 조합해서 풀 수 있는 문제구나!

그래서 풀어보았읍니다.

def main(f=None):
    init(f)
    # sys.setrecursionlimit(10**9)
    # ######## INPUT AREA BEGIN ##########

    N, M = map(int, input().split())
    depend = [0] * N
    G = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        depend[b] += 1

    # ######## INPUT AREA END ############

    pq = []
    for i, e in enu(depend):
        if e == 0:
            heappush(pq, i)

    ans = []
    while pq:
        i = heappop(pq)
        ans.append(i)

        for p in G[i]:
            depend[p] -= 1
            if depend[p] == 0:
                heappush(pq, p)

    print(' '.join(map(str, (i + 1 for i in ans))))