[BOJ 24914 // C++] Split the SSHS

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 24914번 문제인 Split the SSHS이다.
문제는 아래 링크를 확인하자.

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

24914번: Split the SSHS

양 끝 노드가 x, y인 에지 하나의 색을 바꾸는 경우를 생각해보자.

 

주어진 그래프가 트리이므로, 에지의 색이 바뀔 때 이 에지가 포함되어있던 조각은 x가 포함된 조각과 y가 포함된 조각으로 나뉘거나, 조각 개수가 변하지 않거나, 하나만으로 이루어진 조각의 경우 사라지게 된다.

 

마찬가지로 에지에 색을 입힐 때에도 x에 포함된 조각과 y에 포함된 조각이 합쳐지거나, 한쪽 조각에만 연결되거나, 이 에지 하나만으로 생긴 새로운 조각이 생길 수 있다.

 

위의 내용을 유의하여 구현하자.

map을 이용해 그래프를 나타내는 것으로 구현을 편하게 할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;

int N, M, Q;
map<int, int> node[200001];
vector<int> G[200001];
int edge[200000][3]; // 0,1: 두 노드 / 2: color

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> Q;
	int ans = N - 1;
	for (int i = 1; i < N; i++) {
		int x, y, color; cin >> x >> y >> color;
		edge[i][0] = x, edge[i][1] = y, edge[i][2] = color;
		auto &nodex = node[x], &nodey = node[y];
		if (nodex.find(color) == nodex.end()) nodex.insert(make_pair(color, 1));
		else nodex[color]++, ans--;
		if (nodey.find(color) == nodey.end()) nodey.insert(make_pair(color, 1));
		else nodey[color]++, ans--;
	}

	while (Q--) {
		int idx, newcolor; cin >> idx >> newcolor;
		int x = edge[idx][0], y = edge[idx][1], &oldcolor = edge[idx][2];
		auto &nodex = node[x], &nodey = node[y];
		if ((nodex[oldcolor] > 1 && nodey[oldcolor] > 1)) ans++;
		if (nodex[oldcolor] == 1 && nodey[oldcolor] == 1) ans--;
		nodex[oldcolor]--, nodey[oldcolor]--;
		if (!nodex[oldcolor]) nodex.erase(oldcolor);
		if (!nodey[oldcolor]) nodey.erase(oldcolor);

		if (nodex.find(newcolor) == nodex.end()) {
			nodex.insert(make_pair(newcolor, 1));
			if (nodey.find(newcolor) == nodey.end()) {
				ans++;
				nodey.insert(make_pair(newcolor, 1));
			}
			else {
				nodey[newcolor]++;
			}
		}
		else {
			nodex[newcolor]++;
			if (nodey.find(newcolor) == nodey.end()) {
				nodey.insert(make_pair(newcolor, 1));
			}
			else {
				nodey[newcolor]++;
				ans--;
			}
		}

		oldcolor = newcolor;

		cout << ans << '\n';
	}
}