[C++] 1717: 집합의 표현

쩡우·2023년 1월 4일
0

BOJ algorithm

목록 보기
14/65

1717번: 집합의 표현 (acmicpc.net)

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

예제 입력 1

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력 1

NO
NO
YES

풀이

유니온 파인드 문제.
먼저 parent[]라는 배열을 선언한다. i번째 index에는 i의 1단계 위의 부모 원소의 번호가 들어있다.

merge 함수에서는 두 원소 a, b를 받아 그 원소가 들어있는 두 집합을 합친다. a, b 각각의 최상위 부모를 찾아서 둘 중 하나를 같게 만들면, 두 트리가 합쳐진다.
find_parent 함수는 원소 x의 최상위 부모를 찾아 반환한다. 만약 parent[x]와 x가 같다면, x가 최상위 원소이므로 x를 반환한다.
x가 최상위 원소가 아니라면, 최상위 원소를 찾을 때까지 재귀한다. 그 과정에서 찾아지는 모든 원소의 부모를 최상위 원소로 교체한다.

예를 들어, 아래와 같은 트리가 있다고 할 때

find_parent(5)를 수행하고 나면, 아래와 같은 모습으로 변한다.

이렇게 하면 다음 번에 최상위 노드를 찾을 때 여러 번 재귀하지 않아도 돼서 더 빠르다.

코드

#include <iostream>

using namespace std;

int n, m;
int parent[1000001];

void	set_io(void);
void	input_data(void);
void	union_find(void);
int		find_parent(int child);
void	merge(int a, int b);
void	is_in_union(int a, int b);


int main(void)
{
	set_io();
	input_data();
	union_find();

	return (0);
}

void set_io(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	return ;
}

void input_data(void)
{
	cin >> n >> m;
	
	int i = -1;
	while (++i <= n)
		parent[i] = i;

	return ;
}

void union_find(void)
{
	int calculation, a, b;

	int i = -1;
	while (++i < m)
	{
		cin >> calculation >> a >> b;
		if (calculation == 0)
			merge(a, b);
		else if (calculation == 1)
			is_in_union(a, b);
	}

	return ;
}

int find_parent(int x)
{
	if (parent[x] == x) 
		return x;
	parent[x] = find_parent(parent[x]);
	return (parent[x]);
}

void merge(int a, int b)
{
	a = find_parent(a);
	b = find_parent(b);

	if (a > b)
		parent[a] = b;
    else if (a < b)
		parent[b] = a;

	return ;
}

void is_in_union(int a, int b)
{
	if (find_parent(a) == find_parent(b))
		cout << "YES" << '\n';
	else
		cout << "NO" << '\n';
	
	return ;
}


성공 ㅎ-ㅎ
요즘 넘 해이해진 것 같다.. 더 열심히 하자(진짜로)

profile
Jeongwoo's develop story

0개의 댓글