| 유니온 파인드(Union Find) 란? |
- 2가지 연산으로 이루어져 있다.
|
1. Find x : x가 어떤 집합에 포함되어 있는지 찾는 연산 2. Union : x와 y가 포함되어 있는 집합을 합치는 연산 |
- 구현은 트리를 이용한다.
- 가장 처음에는 parent[i] = i로 초기화한다.
[ find 의 구현 ]
//find의 구현
int find(int x)
{
if(x == parent[x])
{
return x;
}
else
{
return find(parent[x]) = find(parent[x]);
}
} [ union의 구현 ]
//union의 구현
//uniond(x, y) : y의 parent를 x로 설정한다.
int union(int x, int y)
{
x = find(x);
y = find(y);
parent[y] = x;
}
| 유니온 파인드 - 집합의 표현 |
1717번: 집합의 표현
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는
www.acmicpc.net
| 유니온 파인드 - 바이러스 |
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
| 유니온 파인드 - 여행 가자 |
1976번: 여행 가자
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인
www.acmicpc.net
| 유니온 파인드 - 공항 |
10775번: 공항
예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불
www.acmicpc.net
| 유니온 파인드 - 친구 네트워크 |
4195번: 친구 네트워크
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진
www.acmicpc.net
'C언어 자료구조' 카테고리의 다른 글
| [ccw] ccw - 선분교차 (0) | 2023.08.03 |
|---|---|
| [비트 마스크] 비트 마스크란? - 4문제 (0) | 2022.07.02 |
| [트리 1일차] 트리의 정의 및 용어 (0) | 2021.03.04 |
| [우선순위 큐 1일차] - 9문제 (0) | 2021.02.25 |
| [우선순위 큐 2일차] - 9문제 (0) | 2021.02.22 |
