[백준] 1717 집합의 표현 (C++)

백준 1717 집합의 표현 문제
백준 1717 집합의 표현 소스코드

📄 문제 설명

Problem

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

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

Input

첫째 줄 : 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이며 같을 수도 있다.)

Output

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

Example Input 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

Example Output 1

NO
NO
YES

📝 문제 해설

이 문제는 주어진 원소들이 같은 집합안에 포하되어 있는지 확인하는 문제로
<Union Find>를 활용해 해결하였다.

▶ 서로소 집합 (Disjoint Set, Union-Find)

교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조

- Union 연산 : 
	어떤 두 원소 a, b에 대해서 union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산

- Find 연산 :
	어떤 원수 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환

서로소 집합 표현

1) 초기화 :

parent 배열에 i 원소에 대한 부모 노드 번호를 저장, 루트 노드인 경우 자기 자신 번호 저장

function initialize()
	for i : 1 ~ N
		parent[i] = i;

2) Union 연산 :

하나의 루트 노드를 다른 하나의 루트 노드의 자식 노드로 넣어 두 집합을 합친다.

function union(a, b)
	aRoot = find(a);
	bRoot = find(b);
	parent[aRoot] = bRoot;

3) Find 연산 :

주어진 원소의 루트 노드 번호를 반환

function find(a)
	if(parent[a] == a) return a;
   	else return find(parent[a]);

</> Source Code

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> parent;

void init() {
	for (int i = 0; i <= n; i++) {
		parent.push_back(i);
	}
}

int find(int a) {
	if (parent[a] == a)return a;
	return parent[a] = find(parent[a]);
}

void unionF(int a, int b) {
	int pa = find(a);
	int pb = find(b);
	parent[pb] = pa;
}

int main() {
	scanf("%d %d", &n, &m);

	init();

	for(int i = 0; i < m; i++){
        int cmd, a, b;
		scanf("%d %d %d", &cmd, &a, &b);
       
		if (cmd == 0) {
			unionF(a, b);
		}
		else {
			if (find(a) == find(b)) {
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}
		}
    }
  
	return 0;
}