[백준 1717] 집합의 표현

글에 개요

백준 알고리즘 1717번 "집합의 표현" 문제입니다.

앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다.

유니온 파인드 (Union-Find)를 정리한 글 내용을 꼭 보시길 추천드립니다!!!!

이 후 이 문제를 통해 확장할 수 있는 알고리즘이 많기 때문에 더더욱 익히셨으면 좋겠습니다. 

[백준 1717] 줄 세우기: https://www.acmicpc.net/problem/1717

참고할 글

1. http://brenden.tistory.com/33 ([알고리즘] 유니온 파인드(Union-Find) 정리글)

핵심 내용

1. 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다.
2. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행해야 한다.
3. Disjoint-set 자료구조를 구현하는 문제입니다.

해결 방법

1. parent[] 배열을 초기화 해줍니다.
2. find(), union(), isSameParent() 메소드를 만들어 줍니다.
3. 여기서 isSameParent()는 임의의 이름으로 만든 함수명입니다. find(), union() 메소드의 작동 원리만 파악하셔도 충분히 푸실 수 있는 문제입니다.

해결한 코드

백준 참고 내용

집합의 표현 성공 스페셜 저지

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	9173	3012	1978	30.586%

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

예제 입력 1 

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력 1 

NO
NO
YES