Union - Find

개념

=> Disjoint Set(서로소 집합) 자료구조를 표현할때 사용하는 알고리즘.

=> 여러 노드가 존재할 때, 두개의 노드를 선택해서 두개의 노드가 하나의 집합에 포함되어 있는지 판별하는 알고리즘

=> Kruskal 알고리즘의 사이클 체크에 사용된다.

=> 다양한 자료구조를 사용해 구현할수 있지만, 가장 편한 트리의 개념을 통해 구현한다.

연산

init()

=> 각 노드를 독립노드로 초기화한다.

find(x)

=> x가 어떤 집합에 포함되어있는지 알려준다.

union(x, y)

=> x가 속한 집합과, y가 속한 집합을 합친다.

if (find(x) == find(y))

std::cout << "같은 집합에 속해있다.";

else

std::cout << "다른 집합에 속해있다";

구현

=>배열의 개념을 통해 구현(각 노드의 대표번호)

//Union Find

#include <iostream>

#include <vector>

#define NUM 7

using namespace std;

vector<int> root;

void Init(int n){

root.resize(n);

for (int i = 1; i < n; i++)

root[i] = i;

}

int Find(int x){

return root[x];

}

void Union(int x, int y){//y를 대표번호로 하는 모든 노드의 대표번호를 모두 x로 설정

int tmp = root[y];

for (int& i : root){

if (i == tmp)

i = root[x];

}

}

int main(){

Init(NUM + 1);

Union(2, 3);

Union(2, 4);

Union(4, 7);

Union(1, 2);

if (Find(1) == Find(7))

cout << "같은 집합에 속해있다." << endl;

else

cout << "다른 집합에 속해있다." << endl;

}

=> 트리의 개념을 통해 구현(각 노드의 루트노드)

//Union Find

#include <iostream>

#include <vector>

#define NUM 7

using namespace std;

vector<int> root;

void Init(int n){

root.resize(n);

for (int i = 1; i < n; i++)

root[i] = i;

}

int Find(int x){//모든 자식노드의 루트를 x로 설정하면서 찾기

if (x == root[x])

return x;

else

return root[x] = Find(root[x]);//경로압축 최적화

}

void Union(int x, int y){

root[Find(y)] = Find(x);//x노드의 자식노드로 y노드를 추가

}

int main(){

Init(NUM + 1);

Union(2, 3);

Union(2, 4);

Union(4, 7);

Union(1, 2);

if (Find(1) == Find(7))

cout << "같은 집합에 속해있다." << endl;

else

cout << "다른 집합에 속해있다." << endl;

}