백준 1717번: 집합의 표현

 

 

Union_find를 활용하는 문제이다.

https://gimmesome.tistory.com/34

[1주차] Union-find

 

 

 

시간 초과를 계속 겪다가 continue를 활용하여 시간을 줄인 코드를 보고 고치다가 틀렸다는 말이 계속 나와 몇번이고 확인하다가 결국 참고한 코드를 그대로 쓰게 됐는데 나중에 알고보니 Yes여서 틀린 거였다는...

영양가 없이 시간을 엄청 잡아 먹었던 문제...

 

 

 

 

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

const int MAX = 1000000 + 1;

int N, M;
int arr[MAX];

int findParent(int num) {
	//재귀함수 사용
	if (arr[num] < 0)
		return num;
	int parent = findParent(arr[num]);
	arr[num] = parent;
	return parent;

	//반복문 사용
	/*
	while(r != arr[r]){
		//arr[r] = arr[arr[r]];
		r = arr[r];
	}
	return r;
	*/
}

void merge(int aParent, int bParent) {
	/*
	부모노드의 배열값은 집합의 크기이고
	나머지 노드의 배열값은 부모노드를 가리킴
	합쳐지면서 부모노드 자리를 뺏긴 노드는 그 배열 값이 
	집합의 크기 --> 부모가된 노드 로 바뀜
	*/

	//집합의 크기가 큰 쪽으로 합쳐짐
	if (abs(arr[aParent]) >= abs(arr[bParent])) {
		arr[aParent] += arr[bParent];
		arr[bParent] = aParent;
	}
	else {
		arr[bParent] += arr[aParent];
		arr[aParent] = bParent;
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	cin >> N >> M;

	for (int i = 0; i <= N; i++) {
		arr[i] = -1;
	}

	for (int i = 0; i < M; i++) {
		int op, a, b;
		cin >> op >> a >> b;
		
		if (op == 0) {
			if (a == b)
				continue;

			int aParent = findParent(a);
			int bParent = findParent(b);

			if (aParent == bParent)
				continue;

			merge(aParent, bParent);
		}
		else {
			if (a == b) {
				cout << "YES\n";
				continue;
			}

			int aParent = findParent(a);
			int bParent = findParent(b);
			if (aParent == bParent)
				cout << "YES\n";
			else
				cout << "NO\n";

		}
	}
	
	return 0;
}