BOJ14676 영우는 사기꾼? - Python

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

골드 4 문제이다.
위상정렬을 활용하면 된다.
건물들을 순서가 있고, 건물을 하나씩만 지을 수 있는것이 아니기에 그것까지 체크해주면 된다.

그리고 건물을 정상적으로 건설하거나, 건설한 만큼의 건물만 파괴되었는지, 또는 건설 할 수 없는 건물을 건설하거나, 건설한적 없는 건물이 파괴되었는지를 체크하면 된다.

from collections import deque

N, M, K = map(int, input().split())

arr = [[] for _ in range(N + 1)] # 관련된 건물
indegree = [0] * (N + 1) # 지을 수 있는지 없는지 차수
build = [0] * (N + 1) # 건물이 지어진 개수
failure = False

for i in range(M):
    first, second = map(int, input().split())
    arr[first].append(second)
    indegree[second] += 1

for i in range(K):
    method, number = map(int, input().split())

    if method == 1: # 건설일 때
        if indegree[number] != 0: # indegree가 0이 아니라면 건설할 수 없는 것이다.
            failure = True
            break

        build[number] += 1 # 지을 수 있으니 개수 1 개 증가

        if build[number] == 1: # 처음 지었을 때만 다음으로 지을 수 있는 건문들의 indegree를 줄여준다.
            for second in arr[number]:
                indegree[second] -= 1
    else: # 파괴일 때
        if build[number] <= 0: # 건설 된 것이 없으면 파괴를 할 수 없다.
            failure = True
            break

        build[number] -= 1

        if build[number] == 0: # 개수가 0개가 되면 관련된 건물들을 못 짓게 해줘야한다.
            for second in arr[number]:
                indegree[second] += 1

if failure:
    print("Lier!")
else:
    print("King-God-Emperor")