문제 72
목표 달성 시점
$1$번부터 $N$번까지 번호가 붙은 정점이 있다. 처음에는 간선이 없으며 $M$개의 간선이 순서대로 추가된다. 간선의 번호는 추가되는 순서대로 $1$부터 $M$까지이다.
$Q$개의 질문에 대해 두 정점이 처음으로 같은 연결 요소에 속하게 되는 간선 번호를 출력하라. 끝까지 같은 연결 요소에 속하지 않는다면 -1을 출력한다.
입력
첫 번째 줄에 세 정수 $N$, $M$, $Q$가 공백으로 구분되어 주어진다. $(2 \le N \le 200\,000; 1 \le M, Q \le 200\,000)$
두 번째 줄부터 $M$개의 줄에 걸쳐 추가되는 간선의 양 끝 정점의 번호를 의미하는 두 정수 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v)$
간선은 추가되는 순서대로 주어진다.
그다음 줄부터 $Q$개의 줄에 걸쳐 각 질문의 두 정점의 번호를 의미하는 두 정수 $a$, $b$가 공백으로 구분되어 주어진다. $(1 \le a, b \le N; a \neq b)$
이미 같은 연결 요소에 속한 두 정점을 잇는 간선이 추가될 수 있다.
출력
각 질문마다 두 정점이 처음으로 같은 연결 요소에 속하게 되는 간선 번호를 한 줄에 하나씩 출력한다. 모든 간선을 추가한 뒤에도 같은 연결 요소에 속하지 않는다면 -1을 출력한다.
예제 입력 1
6 4 5 1 2 3 4 2 3 5 6 1 4 1 5 5 6 2 4 1 6
예제 출력 1
3 -1 4 3 -1
공식 해설
연결성을 바꾸는 간선만 남기기
간선을 추가 순서대로 보면서, 서로 다른 연결 요소를 합치는 간선만 남긴다. 연결 요소는 DSU로 관리한다. 남긴 간선에는 원래의 추가 번호를 가중치로 붙인다.
이미 같은 요소 안의 간선은 연결성을 바꾸지 않으므로 버려도 된다. 따라서 어느 시점에서든 지금까지 남긴 간선들의 연결 요소는 원래 그 시점의 그래프와 같다. 남긴 간선들은 사이클이 없는 숲을 이룬다.
경로의 가장 늦은 간선이 정답
최종 숲에서도 $a$, $b$가 다른 요소에 있으면 끝까지 연결되지 않으므로 답은 $-1$이다. 같은 요소라면 숲에서 두 정점 사이의 경로가 유일하다.
이 경로의 가장 큰 간선 번호를 $t$라 하자. $t$번째까지 추가하면 경로의 모든 간선이 존재하므로 두 정점이 연결된다. 그보다 앞에서는 경로의 간선 하나가 없으므로 숲에서 연결되지 않고, 앞의 연결성 보존에 의해 원래 그래프에서도 연결되지 않는다. 따라서 답은 정확히 $t$이다.
이진 점프로 경로 최댓값 구하기
숲의 각 트리에 루트를 정하고, 각 정점의 $2^k$번째 조상과 그 조상까지 경로의 최대 간선 번호를 전처리한다. 두 배 거리의 정보는 한 배 거리 정보 두 개를 합쳐 구한다.
질의에서는 먼저 깊이를 맞추며 지나간 간선의 최댓값을 누적한다. 이후 두 정점의 조상이 달라지는 가장 큰 점프부터 함께 올라가 최소 공통 조상 바로 아래까지 이동하고, 남은 두 간선도 포함한다.
시간복잡도는 $O((N+M)\alpha(N)+(N+Q)\log(N+1))$, 공간복잡도는 $O(N\log(N+1))$이다. 간선은 읽는 즉시 처리하고 질문도 순서대로 답할 수 있다.
구현 · 언어별 풀이
C++ 구현
DSU로 간선을 읽는 즉시 필요한 간선만 인접 리스트에 저장한다. 조상과 경로 최댓값 표는 $2^k\le N$인 단계까지 잡는다. 각 연결 요소에서 탐색을 시작해 깊이와 바로 위 조상을 채우고, 질문의 두 대표가 다르면 경로 탐색 없이 $-1$을 출력한다.
C 구현
DSU가 서로 다른 연결 요소를 합치는 간선만 숲에 저장한다. 추가 순서를 가중치로 두고 binary lifting의 조상·경로 max 표를 int 배열로 만든다. 긴 트리 전처리는 반복 탐색으로 처리한다.
Python 구현
숲을 반복 DFS로 전처리한다. 조상과 경로 최댓값은 레벨별 array('i')로 두면 $N\log N$개의 객체 비용을 줄일 수 있다. 최종 DSU 루트가 다른 두 정점은 $-1$이고 같은 요소에서는 경로의 최대 간선 번호를 구한다.
Java 구현
조상 int[][]와 경로 max int[][]를 만들고 깊이를 반복 탐색으로 계산한다. 같은 요소를 잇는 추가 간선은 숲에 넣지 않는다. 질의 전 최종 DSU의 연결 여부를 확인한다.
Rust 구현
조상과 경로 최댓값을 레벨별 Vec로 저장한다. 숲의 각 루트에서 반복 DFS하고 두 정점 깊이를 맞춘 뒤 동시에 들어 올린다. 최종 DSU가 다른 질의는 경로 조회 없이 $-1$을 반환한다.
JavaScript 구현
간선을 입력 순서대로 읽으며 DSU로 처음 연결되는 간선만 숲에 넣는다. 각 숲 간선의 값은 추가된 시각인 $1$부터 $M$까지의 정수이다. 최종 DSU에서 두 정점이 다른 집합이면 조회 답은 $-1$이다.
각 나무의 부모·깊이를 반복 DFS로 구하고, 이진 점프 표와 점프 경로의 최대 시각을 Int32Array에 저장한다. 표는 level * (n + 1) + v로 평평하게 두어도 된다.
조회에서는 깊이를 맞춘 뒤 두 정점을 함께 올리며 지나간 경로의 최대 간선 번호를 구한다.