1. 문제설명

$1, 2, …, N$으로 번호가 매겨진 $N$개의 정점이 있다.
다음과 같은 쿼리를 수행한 결과를 출력하라
- 1 u v : 정점 u, v를 잇는 간선 추가
- 2 : 정점의 개수가 가장 많은 트리의 번호 출력
문제 분류
- Data Structure, Set and Map using Tree, Disjoint set

2. 알고리즘 설계

Union-Find 문제이다.
트리가 제거되는 경우는 2가지 이다.
- 사이클이 존재하는 경우
- 2 연산을 수행한 경우
2 연산의 경우 정렬된 {노드 번호, 연결된 자식의 수} 자료에서 가장 앞의 원소를 꺼내면 되겠다.
사이클 처리
- Parent[u], Parent[v]의 자료를 지운다.
- 두 개의 값이 같다면 사이클임을 표시한다.
- 이후, 둘 중 하나라도 사이클이 있다면 자료를 지우고 끝이다.
- 둘 다 사이클이 없다면 연결된 자식 수가 많은 노드를 부모 노드로 취하고, 부모 노드의 연결된 자식 수를 갱신한다.

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 100'002;
int N, Q, P[SZ], Cy[SZ], Size[SZ];

struct T{
	int r, s;
	bool operator<(const T& t) const { return s ^ t.s ? s > t.s : r < t.r; }
};

set<T> S;

int Find(int x) { return P[x] = x == P[x] ? x : Find(P[x]); }
void Merge(int x, int y) {
	S.erase({x, Size[x]});
	S.erase({y, Size[y]});

	Cy[x] += (x == y);

	if(x ^ y) {
		if(Cy[x] + Cy[y]) Cy[x] = Cy[y] = 1;
		else {
			if (x > y) S.insert({ P[x] = y, Size[y] += Size[x] });
      else S.insert({ P[y] = x, Size[x] += Size[y] });
		}
	}
}

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

	cin >> N >> Q;

	for(int i=1; i<=N; i++) S.insert({P[i] = i, Size[i] = 1});

	for(int o, u, v; Q--;) {
		cin >> o;

		if(o == 1) {
			cin >> u >> v;
			Merge(Find(u), Find(v));
		}
		else {
			cout << (*S.begin()).r << '\n';
			S.erase(S.begin());
		}
	}
}

4. 코멘트

이 문제 진짜 너무 어려웠다.
로직 관련
- 먼저 자료를 지운 후, 이후에 다시 추가한다.
  - 처음에는 vector에 사이클이 존재하는 노드를 저장해두었다. 근데, 이렇게 하니까 메모리 초과가 났다…
  - set을 이용한 아이디어는 내가 떠올린 게 아니라, 한참동안 방법을 못 찾겠어서 검색을 통해 확인할 수 있었다.
  - 개인적으로 union-find를 활용한 끝판왕 문제였다.
- x ^ y
  - 이 연산자는 피연산자 2개의 값이 서로 다르면 True이다.
- 2중 저장
  - 아래의 코드를 보면 저장과 동시에 저장하고 있다.
    - S.insert({ P[x] = y, Size[y] += Size[x] });
  - 평소 나였다면, 아래와 같이 작성했을텐데, 상기 코드가 더 깔끔하고 좋은 거 같다.
    - P[x] = y, Size[y] += Size[x], S.insert({P[x], Size[y]});

BOJ 28092. 우선순위와 쿼리

1. 문제설명

2. 알고리즘 설계

3. 전체 코드

4. 코멘트