파이썬 백준 1005 ACM Craft

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
 
testcase = int(input())
for i in range(testcase) : 
    Vn, En = map(int, input().split())
    B = [0] + list(map(int, input().split()))
    V = {}
    child = [0 for i in range(Vn + 1)]
    for i in range(1, Vn + 1) : 
        V[i] = []
    for i in range(En) : 
        v1, v2 = map(int, input().split())
        V[v2].append(v1)
        child[v2] = child[v2] + 1
    start = int(input())
 
    D = [0 for i in range(Vn + 1)]
    def DFS(now) : 
        for next in V[now] : 
            if child[next] == 0 : 
                child[now] = child[now] - 1
                D[now] = max(D[now], D[next] + B[next])
            else : 
                child[now] = child[now] - 1
                DFS(next)
        for next in V[now] : 
            D[now] = max(D[now], D[next] + B[next])
    DFS(start)
    print(D[start] + B[start])

line 7 ~ 17

인풋을 받아 연결관계 dict V와 outdegree 리스트 child를 작성한다.

 

line 19 ~31

전위 순회로 재귀하며 degree가 0인 점부터 i에의 도달시간 D[i]를 갱신한다.

전위 순회를 마친 뒤에는 now의 선행빌드(=child)의 D가 다 fix되었으므로, 그들 중 최댓값이 D[now]가 된다.

(D+B)[start]를 출력한다.