시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 347 | 103 | 72 | 27.273% |
준원이는 스타팅 포인트의 멤버이다. 준원이는 회사에서 병합 (merge) 연산을 수행할 때마다 포인트를 얻는다.
그래서 준원이는 C언어로 다음과 같은 코드를 작성했다.
#include <stdio.h> int par[300001]; int find(int v) { if (v == par[v]) return v; return par[v] = find(par[v]); } void merge(int u, int v){ u = find(u); v = find(v); if (u != v) par[u] = v; } int main() { int N, Q; scanf("%d %d", &N, &Q); for (int i=1; i<=N; i++) par[i] = i; for (int i=1; i<=Q; i++) { int type; scanf("%d", &type); if(type == 1) { int u, v; scanf("%d %d", &u, &v); merge(u, v); } else if(type == 2) { int v; scanf("%d", &v); printf("%d\n", find(v)); } } }
준원이는 위 코드로 다음 문제를 풀었다.
$1$부터 $N$까지 $N$개의 자연수를 원소로 가지는 $N$개의 집합 $\{1\}, \{2\}, \cdots , \{N\}$이 있다.
여러분은 아래와 같이 주어지는 질의를 순서대로 $Q$개 처리해야 한다.
- 1번 질의:
1 u v
의 형식으로 주어진다. 원소 $u$가 속한 집합과 원소 $v$가 속한 집합이 다르다면, 두 집합을 하나로 합친다.- 2번 질의:
2 v
의 형식으로 주어진다. 원소 $v$가 속한 집합에 있는 원소를 아무거나 하나 반환한다.
그런데, 문제가 생겼다. 준원이는 어떤 입력 데이터를 받았는지 까먹었다. 하지만 주어진 $N, Q$ 값과, 2번 질의들이 반환한 값들, 그리고 실행 결과 최종 상태에서의 par[]
배열의 값들은 기억하고 있다.
이 정보를 이용해 어떤 입력 데이터가 주어졌을지 복원해보자.
첫째 줄에 준원이가 기억하는 원소의 개수 $N$과 질의의 개수 $Q$가 공백으로 구분되어 주어진다.
둘째 줄에 실행 결과 최종 상태에서의 par[]
배열의 값들을 의미하는 $N$개의 자연수가 공백으로 구분되어 주어진다.
셋째 줄에 입력 데이터에서 주어진 2번 질의의 개수 $M$이 주어진다.
넷째 줄부터 $M$개의 줄에 걸쳐, 준원이의 코드가 2번 질의들이 반환한 값들이 한 줄에 하나씩 순서대로 주어진다.
준원이의 프로그램이 받았을 입력 데이터를 아래와 같은 형식으로 복원하여 출력한다.
첫째 줄에 원소의 개수 $N$과 질의의 개수 $Q$를 공백으로 구분하여 출력한다.
둘째 줄부터 $Q$개의 줄에 걸쳐, 질의를 한 줄에 하나씩 순서대로 출력한다.
1 u v
의 형식으로 출력한다.2 v
의 형식으로 출력한다.준원이가 기억하는 정보와 일치하는 입력 데이터가 여러 가지 있으면 아무거나 출력해도 된다.
6 7 4 4 4 6 6 6 2 4 6
6 7 1 1 2 1 2 3 1 3 4 2 2 1 5 6 1 1 6 2 6