백준 1717번 _ 집합의 표현

2020-04-06 · 배운 것 · 2분 읽기

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

1717번: 집합의 표현

1. 풀이방법

전형적인 union - find 문제다

2. 코드

#include<iostream>
#include <algorithm>

using namespace std;

int parents[1000005];

void parentsInit(int n)
{
	for (int i = 1; i <= n; i++)
		parents[i] = i;
}

int getParent(int a)
{
	if (parents[a] == a) return a;
	return parents[a] = getParent(parents[a]);
}

void Union(int a, int b)
{
	a = getParent(a);
	b = getParent(b);
	if (a == b) return;
	parents[b] = a;
}

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

	int order, a, b;
	for (int i = 0; i < m; i++)
	{
		cin >> order >> a >> b;
		if (order == 0)
		{
			//a, b를 합친다
			Union(a, b);
		}

		else
		{
			//a, b의 연결여부를 확인한다.
			if (getParent(a) == getParent(b))
				printf("YES\n");
			else
				printf("NO\n");
		}
	}

	return 0;
}

3. 후기

연결여부를 확인할때 배열값을 받는 멍청한 오타를 쳐서 계속 틀렸는데 함수와 비슷해서 정말 찾기 쉽지않았다..

정말 열받았지만

return parents[a] = getParent(parents[a]);

그거 찾으려고 이리 저리 보던 결과 이걸 왜하는지 아직까지 몰랐었는데 트리의 압축을 위해서 한다는 걸 알았기때문에 삽질이었어도 그나마 마음의 위안이 되었다.