Codeforces Round #736 (Div. 2)-C. Web of Lies

문제 설명

$n$명의 귀족이 있다. $1$부터 $n$까지 번호가 붙여져 있는 귀족 $i$는 $i$만큼 힘을 가지고 있다. 또한 $m$개의 친구관계를 가지고 있다. 귀족 $a$와 $b$사이에 있는 친밀도는 항상 서로 작용한다.

만약 한 귀족이 다음 두 조건을 모두 만족하면 그 귀족을 우리는 "취약하다" 고 한다.

• 귀족은 최소 1명 이상의 친구를 가져야한다.
• 모든 귀족의 친구는 그 귀족보다 높은 힘을 가져야한다.

우리는 다음 세종류의 질의에 따라 진행한다.

1. 귀족 $u$와 $v$사이에 친구관계를 맺는다.
2. 귀족 $u$와 $v$사이에 있는 친구관계를 지운다.
3. 다음과정에 따라 답을 도출한다.

The Process: 모든 취약한 귀족을 동시에 죽여버린다. 그리고 그 귀족과 관계되어 있는 친구관계 또한 끝난다. 그후 새로운 귀족이 취약해질 수 있다. 이 과정은 더이상 취약한 귀족이 남아있지 않을 때까지 반복한다. 이 과정은 무한번 반복되지 않는다는 것을 증명할 수 있고, 이 과정이 끝난 이후 남아있는 귀족의 수를 계산해야한다.

단. 답을 도출하고 나서 귀족은 모두 살아나고, 이전까지 남아있던 친구관계는 모두 유지된다.

Input
첫번째 줄에는 귀족의 수와 초기 친구관계의 수를 나타내는 두 정수 $n$과 $m (1 \le n \le 2 \cdot 10^5, 0 \le m \le 2 \cdot 10^5)$ 이 주어진다.

다음 $m$개 줄에 걸쳐서 친구 관계를 나타내는 두 정수 $u$와 $v (1 \le u, v \le n, u \neq v)$가 주어진다.

다음 줄에는 질의의 수 $q (1 \le q \le 2 \cdot 10^5)$가 주어진다.

다음 $q$개 줄에 걸쳐서 질의가 주어지고 각 질의는 다음 세 형식을 따른다.

• $1\;u\;v (1 \le u, v \le n, u\neq v)$ - $u$와 $v$사이에 친구관계를 맺는다. $u$와 $v$는 이 순간에 반드시 서로 친구가 아니다.
• $2\;u\;v (1 \le u, v \le n, u\neq v)$ - $u$와 $v$사이에 친구관계를 지운다. $u$와 $v$는 이 순간에 반드시 서로 친구이다.
• $3$ - 위에 있는 과정을 수행하고 난 답을 출력한다.

Output
$3$타입의 질의가 나올때 마다 답을 출력한다. 반드시 1개 이상의 $3$타입의 질의가 반드시 1개 이상 주어진다.

Example
input
4 3
2 1
1 3
3 4
4
3
1 2 3
2 3 1
3

output
2
1

문제 접근

사용한 알고리즘: 그래프 알고리즘, DAG(Directed Acyclic Graph), 구현
걸린 시간 : 00:18
아니 이런 문제를 어떻게 이렇게 생각할까? 그래프 이론은 아직도 많이 많이 부족하다. 뭐 안부족한 점이 없겠냐만은 그래프 이론은 알아야 할 것도, 아직도 남아있는 지식도 엄청 많이 남아있는 것 같다.

힘이 작은 귀족에서 힘이 큰 귀족으로 화살표를 이어 DAG(방향 그래프)를 만들면, outdegree가 1이상인 귀족은 반드시 결국은 죽는다는 것을 알 수 있다. indegree가 있어도 결국은 indegree로 연결되어 있는 귀족이 죽게 되고 마지막으로 그 귀족 또한 죽는다. 그렇기 때문에 outdegree를 관리하는 배열 하나만 만들어서 그 배열만 관리하면 쉽게 풀 수 있다. 도대체 어떻게 무향 그래프를 유향 그래프로 바꿔서 문제를 쉽게 풀 생각을 할까? 내 알고리즘 문제풀이 데이터베이스에 이 방법이 추가된 것 같다.

친구를 추가할 때는 만약 추가하기 전에 힘이 작은 귀족의 outdegree가 0이면 친구관계를 맺으면서 이 친구는 죽게 되기 때문에 ans값을 1 올려주고, 친구를 삭제할 때는 만약 추가하기전에 힘이 작은 귀족의 outdegree가 1이면 친구관계를 삭제하면서 이 친구는 살게 되기 때문에 ans값을 1 줄여준다. $3$종류의 질의가 끝나면 죽은 귀족은 다시 살아나고 친구관계는 계속 유지되기 때문에 그대로 계속 query를 수행하면 된다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    vector<int> out(n + 1);
    int ans = 0;
    while(m--){
        int a, b; cin >> a >> b;
        out[min(a, b)]++;
        if(out[min(a, b)] == 1) ans++;
    }
    int q; cin >> q;
    while(q--){
        int state; cin >> state;
        if(state == 3){
            cout << n - ans << "\n";
        }else{
            int a, b; cin >> a >> b;
            int cur = min(a, b);
            if(state == 1){
                if(out[cur] == 0) ans++;
                out[cur]++;
            }else{
                if(out[cur] == 1) ans--;
                out[cur]--;
            }
        }
    }
    return 0;
}