백준 1717 집합의 표현 ( c++)

이 문제를 풀면서 먼저 단순히 벡터를 활용해서 숫자를 push하고 그걸 검사하면 된다고 생각했다.
그래서 나온 결론은

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;

	vector<vector<int>> v(n + 1);
	for (int i = 0; i <= n; i++) {
		v[i].push_back(i);
		//그냥 넣기
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		bool isValid = false;
		if (a == 0) {
			int sizeBefore = v[c].size();
			for (int j = 0; j < sizeBefore; j++) {
				v[b].push_back(v[c][j]); // c열의 원소를 b열로 이동
			}
		}
		else if (a == 1) {
			for (int j = 0; j < v[b].size(); j++) {
				if (v[b][j] == c) {
					isValid = true; // b열에 c가 이미 존재하는 경우
					break;
				}
			}
			if (isValid == true) cout << "YES" << '\n';
			else cout << "NO" << '\n';
		}
	}
}

이런 식으로 진행했고 테케에선 정답으로 나왔다.
한번 걸렸던 건 int sizeBefore = v[c].size();
이 부분에서 사이즈를 고정시키지 않았을 때 무한으로 늘어나는걸 잡아줬었다.
그러나 이건 집합의 양방향성을 무시한 잘못된 풀이였다.
이 문제는 유니온 파인드로 해석해야 한다

유니온파인드란?
상호 배타적 부분 집합(서로소 집합)을 표현할 떄 사용
여러 노드가 존재할 때 두 노드를 같은 집합으로 묶어주고 같은 집합에 속하는지 판별하는 것
한마디로 정확히 이 문제와 맞는 대응인듯
부모 노드 지정할 때 parent 배열 선언하고
원소 연결해서 맞추는 것

그래서 다시 푼 결론은

#include <iostream>
#define MAX 1000000 // 원소 최대 개수
using namespace std;

int n, m;
int p[MAX + 1]; // 부모 저장할 배열

//Find 함수 (경로 압축 기법 사용)
int find(int n) {
	if (p[n] < 0) return n; // 자기 자신이 루트면 반환
	p[n] = find(p[n]); // 경로 압축: 부모를 루트로 갱신
	return find(p[n]); // 갱신된 부모 반환
}


//Merge 함수 : 두 집합을 합치는 함수
void merge(int a, int b) {
	a = find(a); // a의 루트 찾기
	b = find(b); // b의 루트 찾기
	if (a == b) return; // 이미 같은 집합이면 합칠 필요 없음
	p[b] = a; // b의 부모를 a로 설정하여 합침
}

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

	fill(p, p + MAX + 2, -1); // 부모 배열 초기화: -1로 설정하여 각 원소가 자기 자신을 루트로 가리키게 함
	int a, b, c;
	cin >> n >> m;
	while (m--) {
		cin >> a >> b >> c;
		if (!a) merge(b, c); // 0이면 b와 c를 합침
		else { //1이면 b와 c가 같은 집합인지 확인
			if(find(b) == find(c)) cout << "YES" << "\n";
			else cout << "NO" << "\n";
		}
	}
}

확실히 무기가 더 필요할 듯 하다