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

문제 링크 => Problem - C - Codeforces

Problem - C - Codeforces

---

이 문제는 그래프를 단순하게 연결하고 끊어야 할것같은 느낌의 문제였지만, 연결하지 않고 현재 정점에서 몇 개가 이어지는지 갯수만 파악하면 해결되는 문제이다.

 

쿼리는 총 3가지로 구성되어 있다.

 

1 u v 로 주어지는 경우 => u와 v가 친구 관계를 맺는다. 즉, 정점을 연결한다고 볼 수 있다.

 

2 u v 로 주어지는 경우 => u와 v가 친구 관계를 끊는다. 즉, 정점을 끊는다고 볼 수 있다.

 

3 으로 주어진 경우 => power에 따라 power가 가장 낮은 순으로 친구관계를 맺은 경우 차례로 kill 을 하는 과정에서 가장 마지막에 살아남는 즉, 친구 관계를 맺을 경우의 power가 가장 높은 사람의 수만 카운팅하면 된다.

 

그렇다면 1, 2, 3을 어떻게 처리하면 좋은지 다음 그림을 통해서 파악해보도록 한다.

 

1번 사람과 2번 사람이 친구 관계를 맺는 경우

이때 1번 사람은 Power가 2번 사람과 관계를 맺음으로써 2번 사람에 비해 power가 낮으므로 1번 사람은 죽게된다.

 

총 4명의 사람 중에 결국 1번 사람이 죽음으로써 3명의 사람이 살아남게 된다.

 

1번 사람과 3번 사람이 친구관계를 맺은 경우

1번 사람과 3번 사람이 친구 관계를 맺음으로써 1번 사람은 총 2명의 사람과 친구 관계가 되었음을 알 수 있다.

 

그러나 죽는 경우는 위와 동일하게 1번 사람 한명 밖에 없다.

 

따라서 친구 관계를 처음으로 맺게 되는 경우에 대해서 power가 더 낮은 사람이 친구 관계를 1번 맺게 되는 경우 총 인원수에서 1명 감소하는 것과 2번 이상 맺게 되는 경우는 변경사항이 없음을 알 수 있다.

 

3번 사람과 4번 사람이 친구 관계를 맺는 경우

위에 있던 방식을 그대로 적용해보면, 3번 사람과 4번 사람이 친구 관계를 맺음으로써 power가 낮은 3번 사람이 처음으로 친구 관계를 맺게 되는 경우이므로 죽임을 당하는 사람이 한명 더 늘었음을 알 수 있다.

 

이를 역으로 적용해본다면 친구 관계를 끊는 경우 power가 낮은 사람이 친구 관계가 없어지는 경우에 대해서 죽임을 당하지 않는다는 것 또한 확인할 수 있다.

 

따라서 이러한 과정을 코드로 작성하면 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int Map[200001];
int result = 0;
int n, m;

void test() {

	cin >> n >> m;
	result = n;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		if (x > y) {
			Map[y]++;
			if (Map[y] == 1) result--;
		}
		else {
			Map[x]++;
			if (Map[x] == 1) result--;
		}
	}

	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int op;
		cin >> op;
		if (op == 3) {
			cout << result << endl;
		}
		else {
			int x, y;
			cin >> x >> y;
			if (op == 1) {
				if (x > y) {
					Map[y]++;
					if (Map[y] == 1) result--;
				}
				else {
					Map[x]++;
					if (Map[x] == 1) result--;
				}
			}
			else {
				if (x > y) {
					Map[y]--;
					if (Map[y] == 0) result++;
				}
				else {
					Map[x]--;
					if (Map[x] == 0) result++;
				}
			}
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	test();

	return 0;
}