[백준][union find] 1717 집합의 표현 c++ 구현

목차

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

1717번: 집합의 표현

문제

 

 

 

 

 

보기 전에 참고하면 좋을 것 같습니다

https://be-senior-developer.tistory.com/29

[Union find] c++ 구현 및 설명

 

 

문제 접근

최적의 탐색 조건을 만들어 주지 않으면 시간 초과로 틀리는 문제로

union find알고리즘을 잘 구현해주면 풀 수있는 문제였다.

 

 

 

코드구현

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

vector<pair<int, int>> parent(1000000, make_pair(0, 0));  //노드와 높이를 저장해 놓는다.

int n, m;
int find_root(int node) {

	if (parent[node].first == node)
		return node;
		//노드의 최적화: 항상 부모를 루트노드로 만듬

	return parent[node].first = find_root(parent[node].first);

}

void combine_tree(int node1, int node2) {
	int root1 = find_root(node1);
	int root2 = find_root(node2);

	if (root1 != root2) {   //서로소 집합이면 실행한다.
		if (parent[root1].second < parent[root2].second) {   //높이가 낮은 트리를 높은트리에 붙인다.
			parent[root1].first = root2;
		}
		else if (parent[root1].second > parent[root2].second){
			parent[root2].first = root1;
		}
		else {
			parent[root1].first = root2;
			parent[root2].second++;
		}
			

	}

}

int main() {
	ios_base::sync_with_stdio(false); // c와 c++의 표준 입출력 스트림을 동기화를 하지않아 속도 향상
	cin.tie(nullptr); // cin사용시 출력 버퍼를 비우지(flush) 않는다.
	cout.tie(nullptr);  // 위와 동일

	int node1, node2, i, j, relation;
	cin >> n >> m;
	for (i = 0; i <= n; i++) {
		parent[i].first = i;
		//parent[i].second = 0;
		
	}

	for (i = 0; i < m; i++) {
		cin >>relation>> node1 >> node2;
		if (relation == 0)
			combine_tree(node1, node2);
		else {
			if (find_root(node1) != find_root(node2))
				cout << "NO" << "\n";
			else
				cout << "YES" << "\n";
		}
	}

	
}