유니온 파인드

1. 함수의 구성

유니온 파인드는 find와 union 두가지 함수로 구성이 된다.

(1) find는 그래프에서 루트노드를 찾아주는 함수이다.

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

 

(2) union은 서로 연결되어 있지 않은 그래프를 연결시키는 함수이다.

void Union(int x, int y){
	x = find(x);
	y = find(y);
	if(x!=y){
		parent[y] = x;
	}
}

 

 

2. 함수의 사용

유니온 파인드는 아래의 두가지 경우에 사용할 수 있다.

(1) 그래프가 연결되어 있는지 확인할 때 (ex [boj]1717_집합의 표현)

어떤 두 노드의 루트노드가 같다면 두 노드는 한 그래프 안에 있음을 보장받는다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int parent[1000001];


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[x] = y;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	int n, m;
	int op, a, b;

	cin >> n >> m;
	for (int i = 0; i < n+1; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < m; i++) {
		cin >> op >> a >> b;
		if (op == 1) {
			if (find(a) == find(b)) { //루트노드가 같다면?!
				cout << "YES\n";
			}
			else {
				cout << "NO\n";
			}
		}
		else {
			uni(a, b);
		}
	}

	return 0;
}

 

(2) 사이클이 존재하는지를 확인할 때. (ex [boj]1922_네트워크연결)

크루스칼 알고리즘에서는 두 노드를 연결했을때 사이클이 생기는지 확인해야 하는 순간이 있다. 이때 유니온 파인드를 이용할 수 있다.

어떠한 두 노드의 루트노드가 같다는 것은 두 노드가 한 그래프로 이어져 있다는 것을 뜻한다.

이때 두 노드를 연결하면 닫힌 그래프, 즉 사이클이 생긴다.

따라서 루트노드가 같은 두 노드를 연결하면 사이클이 생긴다는 것을 알 수 있다.

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

using namespace std;

int parent[1001];

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

void uni(int x, int y) {
	x = find(x);
	y = find(y);
	parent[x] = y;
}

bool cmp(vector<int> v1, vector<int> v2) {
	if (v1[2] < v2[2]) {
		return true;
	}
	else {
		return false;
	}
	//return v1[2] < v2[2];
}

int main() {
	vector<vector<int>> node;
	int n,m;
	cin >> n >> m;
	stack<int> s;

	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		node.push_back({ a,b,c });
	}

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	
	sort(node.begin(), node.end(), cmp);

	int temp1, temp2, cnt=0, ans=0;
	for (int i = 0; i < node.size(); i++) {
		temp1 = find(node[i][0]);
		temp2 = find(node[i][1]);
		// 루트노드가 다르다면 (연결해도 사이클이 생기지 않는다면)
		if (temp1 != temp2) {
			uni(temp1, temp2);
			cnt++;
			ans += node[i][2];
			// 노드개수-1 = 간선개수
			if (cnt == n - 1) {
				break;
			}
		}
	}
	cout << ans;

	return 0;
}

 

* 싸이클이 생기는지 확인하는 또다른 방법은 stack을 이용하는 것이다. 아래를 참조한다

https://blog.naver.com/ngoodsamari?Redirect=Log&logNo=221607542218&from=postView