CodeDrive

문제:

초기에 {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를 출력해도 된다.)

풀이방법:

 단순해 보이지만 정답 비율이 낮았기에 효율적으로 풀어야 하는 것이 중요할 것 같았다. 그리고 알아보니 이 문제는 Union-Find를 사용해서 풀어야 하는 문제였다.

 우선 parents 초기화 함으로써 해당 인덱스의 값이 각 집합을 이루고 있다고 가정했다. union은 합치는 명령을, find는 해당 집합에서 parent를 찾도록 하는 연산으로 정의했다.

이 문제는 다음과 같은 기준으로 해결된다.

1. 초기에는 각 집합이 하나의 값으로 집합을 이루고 있고, 이를 각각 parent라고 정의한다.

2. union 연산이 0 a b와 같이 들어온다면 b의 parent를 a의 parent에 연결한다.(혹은 가리킨다.)

3. find는 parents에서 인덱스를 조회했을 때, 입력 값과 같다면 parent이기 때문에 이를 바로 return해주고(이는 처음 parents의 정의이다.), 그렇지 않다면 find를 재귀적으로 사용해서 입력의 값의 parent를 찾도록 한다.

4. check는 1 a b와 같이 들어왔을 때, a와 b를 각각 find 연산을 사용해서 parent가 같은지 확인한다. (같으면 True, 다르면 Faslse)

문제링크:

https://www.acmicpc.net/problem/1717