[개념] Union-Find 기법

그래프

노드와 노드사이에 연결된 간선의 정보를 가지고 있는 자료구조

ex ) 여러개의 도시가 연결되어 있다

 

 

그래프 구현 방법

1. 인접 행렬 : 2차원 배열을 사용
2. 인접 리스트 : 리스트를 사용

두가지 방식 특징 ( 노드의 갯수 V, 간선의 갯수 E인 그래프)

인접 행렬 이용

• 장점 - 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 $O(1)$의 시간으로 즉시 알수 있음
• 단점 - 간선 정보를 저장하기 위해 $O(V^2)$ 만큼의 메모리 공간이 필요

인접 리스트 이용

• 장점 - $O(V)$만큼의 시간 소요
• 단점 - 간선의 개수만큼 $O(E)$만큼의 메모리 공간 필요

---

서로소 집합 (유니온 파인드 - Union find)

공통 원소가 없는 두 집합

union - 합집합 연산 - 2개의 원소가 포함된 집합을 하나의 집합으로 합침

find - 찾기 연산 - 특정 원소가 속한 집합이 어떤 집합인지 알려줌

트리 자료 구조 이용

1. union(합집합) 연산을 확인하여, 서로 연결된 두 노두 A,B 확인
   1. A와 B의 루트 노드 A', B'를 찾음
   2. A'를 B'의 부모 노드로 설정
2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정 반복

(A', B' 중 보통 더 작은 숫자가 부모가 됨)

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<memory.h>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

int parent[MAX];
int V, E;
int findParent(int num) {
    if (num == parent[num]) return num;
    findParent(parent[num]);
}
void func(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> V >> E;
    for (int i = 1; i <= V; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < E; i++) {
        int a, b;
        cin >> a >> b;
        func(a, b);
    }
    // 각원소가 속한 최상위 집합
    int cnt = 0;
    for (int i = 1; i <= V; i++) {
        cout << findParent(i) << " ";
    }
    cout << "\n";
    // 각원소의 부모 테이블
    for (int i = 1; i <= V; i++) {
        cout << parent[i] << " ";
    }

}

⇒ 해당 코드는 만약 하나의 그래프로 쭉~연결되어 있다면 최대 O(V)시간이 걸릴 수 있다

노드개수가 V이고 find 혹은 union연산 개수가 M개인 경우 전체 시간복잡도는 O(VM)이 되어 비효율적임

find 과정을 최적화 하는 법

• 경로 압축기법 - 재귀적 호출한 뒤 부모 테이블값 갱신

int findParent(int num) {
    if (num == parent[num]) return num;
    return parent[num] = findParent(parent[num]);
}

서로소 집합을 활용한 사이클 판별

무방향 그래프 내에서의 사이클 판별할 때 사용

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인
   1. 루트 노드가 서로 다르면 두 노드에 대해 union연산 수행
   2. 루트 노드가 서로 같다면 사이클 발생
2. 그래프에 포함되어 있는 모든 간선에 대해 1번 과정 반복

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <deque>
#include <stack>
#include <vector>
#include<cstdio>
#include<algorithm>
#include<memory.h>
#include<queue>
#include<map>
#define MAX 100001
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

int parent[MAX];
int V, E;
int findParent(int num) {
	if (num == parent[num]) return num;
	return parent[num] = findParent(parent[num]);
}
void func(int a, int b) {
	a = findParent(a);
	b = findParent(b);
	if (a > b) parent[a] = b;
	else parent[b] = a;
}
int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> V >> E;
	bool check;
	for (int i = 1; i <= V; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < E; i++) {
		int a, b;
		cin >> a >> b;
		if (findParent(a) == findParent(b)) {
			check = false;
		}
		else {
		func(a, b);
		}
	}
	if (check) {
		cout << "사이클 없음";
	}
	else {
		cout << "사이클 있음";
	}

}