77. 친구인가? (Union & Find 자료구조) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★

#include <stdio.h>

using namespace std;

int a[1001];

int Find(int x)
{	
	if(x == a[x]) return x;
	else return a[x] = Find(a[x]); // 3. 같은 루트노드를 가지는 원소 묶기(트리 구조 단순화) 
}


void Union(int x, int y)
{
	int z = Find(x);
	int w = Find(y);
	if(z != w) a[z] = w;
}


int main()
{
	int n, m, x, y, q, w;
	scanf("%d %d", &n, &m);
	
	for(int i = 1; i <= n; i++)
		a[i] = i; // 1. 초기화 
		
	for(int i = 1; i <= m; i++)
	{
		scanf("%d %d", &x, &y);
		Union(x, y); // 2. 각 데이터 합하기, 트리화 
	}
	
	scanf("%d %d", &q, &w);
	
	if(Find(q) == Find(w))
		printf("YES");
	else
		printf("NO");
		
	return 0;
	
}

1. Union & Find 알고리즘은 Disjoint-set을 활용한 알고리즘이다.

• Disjoint Set이란
  서로 중복되지 않는 부분집합으로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
  
  즉, 공통 원소가 없는, 즉 “상호 배타적” 인 부분 집합들로 나눠진 원소들에 대한 자료구조이다.
  서로소 집합 자료구조라고도 한다.
• Union-Find란
  집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리 구조를 이용하여 구현한다.
• Union-Find의 연산
  아래의 세 가지 연산을 이용하여 Disjoint Set을 표현한다.
  1. make-set(x)
   : 초기화, x를 유일한 원소로 하는 새로운 집합을 만든다.
  2. union(x, y)
  : 합하기, x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산
  3. find(x)
  : 찾기, x가 속한 집합의 대표값(루트 노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산

경로 압축