유니온파인드(Union Find)란 |
- 대표적인 그래프 알고리즘으로 합집합 찾기 라는 의미를 가지고 있다.
- 상호배타적집합(Disjoint-set) 이라고도 한다.
- 여러개의 노드가 있을때 두개의 노드가 같은 그래프에 속하는지 판별하는 알고리즘
- 2가지 연산으로 이루어져 있다.
단계 1. 주어진 원소들이 서로 같은 집합에 속하는가를 알아내고(Find)
단계 2. 만약에 그렇지 않으면 같은 집합에 속하도록 추가하라(Union)
유니온파인드 구현방법 |
예)
위와 같은 경우 union(1,5),union(4,5),union(2,3),union(2,7),union(3,7),union(6,7) 을 표현한 그래프
이러한 그래프에 connected component 는 {0},{1,4,5},{2,3,6,7} 이렇게 3개의 그룹으로 나뉜다
여기에 2와 5를 연결해 보자
구현하는 방법은 다음과 같다.
1단계) 각 ID 에 그룹 번호를 자신의 ID로 그룹 번호 결정
2단계) union(1,5) 를 수행하기 위해서 Find(1)=1 과 Find(5)=5 의 서로 다른 그룹을 같게 만든다.
3단계) union(4,5) 를 수행하기 위해서 Find(4)=4 과 Find(5)=1 의 서로 다른 그룹을 같게 만든다.
이때 Find(5) 에서 1을 찾는 규칙은 다음과 같다.
Find(5)->Find(1) 에서 찾고자 하는 자신의 번호와 그룹의 번호가 같으면 해당 번호가 자기 그룹이기 때문에 그룹번호를 리턴한다.
4단계) union(2,3) 를 수행하기 위해서 Find(2)=2 과 Find(3)=3 의 서로 다른 그룹을 같게 만든다.
5단계) union(2,7) 를 수행하기 위해서 Find(2)=2 과 Find(7)=7 의 서로 다른 그룹을 같게 만든다.
5단계) union(3,7) 를 수행하기 위해서 Find(3)=2 과 Find(7)=2 에서 이미 같은 그룹이기 때문에 굳이 union을 수행할 필요가 없다.
6단계) union(6,7) 를 수행하기 위해서 Find(6)=6 과 Find(7)=2 의 서로 다른 그룹을 같게 만든다.
6단계가 끝나면 {0},{1,4,5},{2,3,6,7} 이러한 모습이 된다.
7단계) union(2,5)를 수행하기 위해서 find(2)=2,find(5)=1 이기 때문에 서로 다른 그룹을 같게 만들면 다음과 같은 형태가 된다.
위와 같이 되는데 여기서 Find(6)=1 이 되는 원리는 Find(6)->Find(2)->Find(1)을 찾아가기 때문에 Find(6)=1 이 나오게 된다.
문제풀이 |
http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2265&sca=60&s1=&s2=&s3=&s4=
이문제는 모두 끊어져 있다고 생각하고 뒤에서 부터 삭제 명령이 들어 왔다면 이어주면 되는 Union Find 형태의 알고리즘 유형이다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
#include <stdio.h>
using namespace std;
#define MAXN 200200
int N,Q;
int parent[MAXN],group[MAXN],q[MAXN*2][3],ans[MAXN*2];
int find(int node)
{
if(node!=group[node]) group[node]=find(group[node]);
return group[node];
}
int main()
{
int i;
//freopen("input.txt","r",stdin);
scanf("%d %d",&N,&Q);
Q+=N-1;
group[1]=1;
for(i=2;i<=N;i++)
{
scanf("%d",&parent[i]);
group[i]=i;
}
for(i=1;i<=Q;i++)
{
scanf("%d %d",&q[i][0],&q[i][1]);
if(q[i][0]==1) scanf("%d",&q[i][2]);
}
for(i=Q;i>=1;i--)
{
if(q[i][0]==0) group[q[i][1]]=parent[q[i][1]];
else if(find(group[q[i][1]])==find(group[q[i][2]])) ans[i]=1;
}
for(i=1;i<Q;i++)
{
if(q[i][0]==0) continue;
if(ans[i]==1) printf("YES\n");
else printf("NO\n");
}
return 0;
}
|
cs |
'강의자료 > 알고리즘' 카테고리의 다른 글
[자료구조]Dynamic Segment Tree (6) | 2022.10.04 |
---|---|
[알고리즘]A*(a스타) 알고리즘 (8) | 2022.07.14 |
[자료구조]스택(Stack) (8) | 2022.04.05 |
SCC(Strongly Connected Components)-코세라주 알고리즘 (8) | 2022.03.23 |
최소 공통조상 LCA(Lowest Common Ancestor) 알고리즘 (12) | 2022.02.08 |