상호 배타적 집합, Disjoin-set(서로소 집합) 이라고도 부른다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다.
주로 집합을 관리하는 자료구조로, 여러 개의 원소들이 각각 다른 집합에 속해 있는지 여부를 빠르게 찾거나(Find), 두 집합을 하나로 합치는(Union) 연산을 효율적으로 수행할 수 있습니다. 이 자료구조는 서로소 집합 문제를 해결하기 위해 만들어졌습니다
크루스칼 알고리즘과 프림 알고리즘을 알기 위해선 유니온 파인드 알고리즘을 알아야 한다.
유니온 파인드 알고리즘은 두가지의 연산을 진행한다. 이 연산 과정을 Union, Find라고 부른다.
Union-Find (또는 Disjoint Set)와 MST(최소 신장 트리, Minimum Spanning Tree)는 서로 다른 알고리즘/자료구조입니다. 하지만 Union-Find 자료구조는 MST를 찾는 Kruskal 알고리즘에서 핵심적으로 사용되기 때문에 두 개념이 함께 등장하는 경우가 많습니다.
오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다. 모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계 가 번호로 표현된 숫자쌍이 주어진다. 만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다. 그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다. 학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램 을 작성하세요. 두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다.
1번 학생과 2번학생이 친구이며 2번 학생과 3번 학생이 친구. 3번 학생과 4번 학생이 친구이다. 그리고 5번 학생과 6번학생이 친구라면 다음과 같이 그래프로 표현 할 수 있다. 이 두 집합은 공통원소가 없기 때문에 서로소집합 즉 Disjoin-set이라 볼 수 있다. 이것을 판별하는 알고리즘이 Union Find 알고리즘이다.
입력 예제
9 7
1 2
2 3
3 4
1 5
6 7
7 8
8 9
3 8 // 친구인지 검사하는 입력 예제
출력 예제
NO
