백준 14676 영우는 사기꾼?

문제 URL : https://www.acmicpc.net/problem/14676

14676번: 영우는 사기꾼?

 

문제 접근법 : 

위상정렬을 이용한 문제입니다.

해당 건물을 건설할때 indegree가 없어야 건설을 할수있고

건설한후 해당 참조하고있는 indegree를 줄여줍니다.

그리고 건물을 건설했다는것을 알려주고요

 

해당건물을 파괴할땐 건물이 지어졌는지 확인해야합니다.

그리고 건물을 파괴한후 남아있는 건물이 없다면 다시 indegree를 채워줘야겠쬬?

 

소스코드 : 

#include<bits/stdc++.h>
using namespace std;
int indegree[100001];
int n,m,k;
vector<int> v[100001];
vector<pair<int,int>> vk;
void input(){
    cin>>n>>m>>k;
    int a,b;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        indegree[b]++;
        v[a].push_back(b);
    }
    for(int i=0;i<k;i++){
        cin>>a>>b;
        vk.push_back({a,b});
    }
}
void solve(){
    vector<int> build(n+1);
    for(auto [a,b]:vk){
        if(a==1){
            if(indegree[b]){
                cout<<"Lier!\n";
                return;
            }
            if(build[b]==0)
            for(int next:v[b])if(indegree[next])indegree[next]--;
            build[b]++;
        }
        else{
            if(!build[b]){
                cout<<"Lier!\n";
                return;
            }
            build[b]--;
            if(!build[b]){
                for(int next : v[b])indegree[next]++;
            }
        }
    }
    cout<<"King-God-Emperor"<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    input();
    solve();
}

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.