[백준] 14676 영우는 사기꾼? c++

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

14676번: 영우는 사기꾼?

풀이과정

이때까지 풀었던 문제 유형들과는 다른 느낌이었다.  
위상 정렬 함수를 만들지 않고 main함수 안에서 하려고 하니 더 어렵게 느껴졌다.

일단 입력을 M번 받아놓고 화살표 간선끼리 연결해주며 진입 차수도 플러스해준다.  
그다음, K번 반복하는 부분이 중요한데 option이 1이면 건물을 1개 건설하는 것이고 2이면 파괴하는 것이라고 한다.

건설 부분을 보면 진입 차수가 0이여만 construct가 가능하다. 1번 노드를 건설했으니 next 2번, 3번 노드도 건설 가능하도록 진입 차수를 -1씩 해준다. 만약에 진입 차수가 0이 아닌데 건설을 하려고 한다면 건설할 수 없는 건물을 건설한다는 뜻이므로 check를 true로 바꿔준다.

파괴 부분을 보면 건설한 construct가 1개 이상이여야만 가능하다. 파괴를 하므로 construct를 -1씩 해준다. construct가 0이면 건물이 모두 파괴되었다는 뜻이므로 다음 노드를 지을 수 없기 때문에 다음 노드의 진입 차수를 +1 해준다.(진입 차수가 0이어야만 construct가 가능하기 때문)

 

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

int N, M, K, x, y, option, a;
int indegree[100001], construct[100001];
bool check;

vector <int> v[100001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		v[x].push_back(y);
		indegree[y]++;
	}
	for (int i = 0; i < K; i++) {
		cin >> option >> a;
		if (option == 1) { // 건설
			if (indegree[a] == 0) {
				construct[a]++;
				if (construct[a] == 1) {
					for (int j = 0; j < v[a].size(); j++) {
						int next = v[a][j];
						indegree[next]--;
					}
				}
			}
			else check = true;
		}
		else if (option == 2) { // 파괴
			if (construct[a] > 0) {
				construct[a]--;
				if (construct[a] == 0) {
					for (int j = 0; j < v[a].size(); j++) {
						int next = v[a][j];
						indegree[next]++;
					}
				}
			}
			else check = true;
		}
	}

	if (check) cout << "Lier!";
	else cout << "King-God-Emperor";
}