문제 47
이분 매칭 2
왼쪽 그룹에는 $1$번부터 $N$번까지, 오른쪽 그룹에는 $1$번부터 $M$번까지 번호가 붙은 정점이 있다.
서로 다른 그룹에 속한 두 정점을 연결하는 $K$개의 간선이 주어진다.
서로 끝점을 공유하지 않도록 간선을 선택할 때 선택할 수 있는 간선 개수의 최댓값을 구하라.
입력
첫 번째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $(1 \le N, M \le 100\,000; 0 \le K \le 500\,000)$
두 번째 줄부터 $K$개의 줄에 걸쳐 각 간선이 연결하는 왼쪽 그룹과 오른쪽 그룹의 정점 번호를 의미하는 두 정수 $a$, $b$가 공백으로 구분되어 주어진다. $(1 \le a \le N; 1 \le b \le M)$
같은 두 정점을 연결하는 간선은 두 번 이상 주어지지 않는다.
출력
선택할 수 있는 간선 개수의 최댓값을 출력한다.
예제 입력 1
4 4 7 1 1 1 2 2 1 2 3 3 2 3 4 4 3
예제 출력 1
4
예제 입력 2
3 5 0
예제 출력 2
0
공식 해설
양쪽 정점 수가 각각 $100\,000$, 간선 수가 $500\,000$까지 커질 수 있어 각 정점마다 독립적으로 전체 간선을 탐색하는 방법은 적절하지 않다. 최단 증강 경로 여러 개를 한꺼번에 처리하는 방법이 필요하다.
최단 증강 경로를 묶어서 찾기
선택되지 않은 간선과 선택된 간선을 번갈아 따라가며, 짝이 없는 왼쪽 정점에서 짝이 없는 오른쪽 정점에 도착하는 경로를 증강 경로라고 한다. 경로 위 간선의 선택 여부를 뒤집으면 매칭 크기가 $1$ 증가한다.
정점마다 따로 긴 탐색을 반복하기보다 홉크로프트–카프 알고리즘으로 현재 가장 짧은 증강 경로들을 한 단계에 함께 찾는다. 양쪽 정점의 현재 짝을 배열에 저장한다.
BFS와 DFS의 역할
짝이 없는 왼쪽 정점들을 모두 거리 $0$으로 두고 BFS한다. 왼쪽 $u$에서 오른쪽 이웃 $v$로 갔을 때 $v$에 짝이 있으면 그 짝인 왼쪽 정점으로 이동한다. 이때 왼쪽 정점의 거리가 $1$ 늘어난다. 짝이 없는 오른쪽 정점에 도착하는 가장 짧은 거리도 기록한다.
DFS는 이 거리 정보가 증가하는 방향만 따라가고, BFS에서 찾은 최단 거리에서 만난 비매칭 오른쪽 정점에서만 성공하도록 한다. 성공한 경로는 돌아오면서 짝을 바꾼다. 한 단계에서는 서로 정점을 공유하지 않는 최단 증강 경로들을 더 찾을 수 없을 때까지 찾는다.
이미 실패한 왼쪽 정점이나 확인이 끝난 간선을 같은 단계에서 반복 탐색하지 않도록 처리하면 한 단계에 각 간선을 상수 번만 확인한다. 새 단계에서는 거리와 탐색 상태를 다시 만든다.
최적성과 복잡도
더 큰 매칭과 현재 매칭의 서로 다른 간선들을 비교하면, 크기가 더 큰 쪽의 간선이 하나 많은 교대 경로가 생긴다. 이것이 현재 매칭의 증강 경로이므로 증강 경로가 없다면 현재 매칭이 최대이다.
한 단계에서 최단 경로들을 막고 나면 다음 증강 경로의 길이는 증가한다. $V=N+M$, $E=K$라 하자. 길이가 $\sqrt V$를 넘은 뒤에는 서로 겹치지 않는 증강 경로가 $O(\sqrt V)$개만 남을 수 있다. 그 전 단계 수도 $O(\sqrt V)$이므로 전체 단계 수는 $O(\sqrt V)$이다.
시간복잡도는 $O((V+E)\sqrt V)$, 공간복잡도는 $O(V+E)$이다.
구현 · 언어별 풀이
C++ 구현
양쪽의 짝, 왼쪽 정점의 거리, 다음에 볼 간선 위치를 vector<int>로 관리한다. 짝이 없는 상태는 $-1$로 통일한다. DFS는 BFS에서 정한 최단 종료 거리까지만 성공시키고, 한 단계에서 이미 실패한 정점은 다시 탐색하지 않는다. 긴 경로에는 정점과 다음 간선 위치를 명시적 스택에 저장해 호출 깊이를 피할 수 있다.
C 구현
양쪽 match, BFS 거리, 현재 간선 위치를 int 배열에 둔다. BFS가 찾은 최단 증가 경로 길이까지만 DFS를 수행한다. 긴 경로를 위한 명시적 스택으로 한 단계의 매칭 변경을 복원할 수 있다.
Python 구현
양쪽 match와 level을 배열로 두고 deque로 BFS한다. DFS에는 명시적 스택을 사용해 최대 100000 깊이의 재귀를 피한다. 같은 BFS 단계에서 실패한 정점의 level을 무효화해 재탐색을 줄인다.
Java 구현
int[] match와 level, next를 사용한다. BFS 뒤 같은 level 관계의 간선만 탐색하며 DFS는 반복문으로 작성한다. 많은 간선에 Integer 객체를 하나씩 만들기보다 primitive 인접 배열을 쓴다.
Rust 구현
match와 level을 Vec에 두고 BFS에는 VecDeque를 사용한다. 최단 증가 경로만 명시적 스택으로 찾고, 성공하면 경로를 따라 양쪽 match를 함께 바꾼다. 실패한 정점은 해당 단계에서 다시 탐색하지 않는다.
JavaScript 구현
양쪽 짝과 거리, 현재 이웃 위치를 Int32Array로 저장한다. BFS는 짝이 없는 왼쪽 정점을 모두 넣어 시작하고 가장 짧은 증강 경로 길이를 구한다. 큐는 배열과 head로 처리한다.
DFS는 해당 레벨을 따라 명시적 스택으로 진행하여 깊이 $100\,000$의 재귀를 피한다. 같은 단계에서 실패한 정점은 거리 표식을 무효화하고 이웃 인덱스를 재사용한다. 빈 오른쪽 정점을 만났더라도 BFS의 최단 종료 거리와 맞을 때만 경로를 뒤집는다. 긴 증강 경로를 먼저 선택하면 단계당 간선 처리와 공통 풀이의 복잡도 보장을 잃는다.