[백준 1717번 / C++ / find-union] 집합의 표현

[백준 1197번 / C++ / 크루스칼] 최소 스패닝 트리

---

 

크루스칼 알고리즘이랑 99.9 % 동일하다고 보면 된다. 

 

#접근방법 

1. 먼저 parent 배열을 인덱스 번호로 초기 세팅 해준다. 
2. 입력값 b와 c 가 주어진다면 현재 b와 c를 인덱스로 가지는 parent 배열을 확인한다. 
3. 각자의 부모의 번호가 다르면 uion 해준다. (부모 번호 동일하게 세팅)  
4. 같은 집합체인지를 묻는다면 b와 c를 인덱스로 가지는 parent 배열에서 부모의 번호가 같다면 "YES" , 부모의 번호가 다르다면 "NO" 출력

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
vector <int> parent; 

int find(int x) {
	if (parent[x] == x)return x;
	else return parent[x] = find(parent[x]);
}
void uni(int x, int y) {
	x = find(x); 
	y = find(y); 
	parent[y] = x; 
}
bool sameparent(int x, int y) {
	x = find(x); 
	y = find(y); 
	if (x == y)return true;
	else return false; 
}
int main() {
	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0); 
	int vertex, m; cin >> vertex >> m; 
    parent.resize(vertex + 1, 0); 
	for (int i = 1; i <= vertex; i++)parent[i] = i; 
	while (m--) {
		int a, b, c; 
		cin >> a >> b >> c; 
		if (!a) {
			//union
			if (sameparent(b, c) == false) {
				uni(b, c); 			
			}		
		}
		else {
			//check
			if (sameparent(b, c) == false) cout << "NO\n";			
			else cout << "YES\n";		
		}
	}
}

 

1717번: 집합의 표현