일반 그래프 최대 매칭 복원

이분 그래프가 아닌 일반 그래프에서는 홀수 사이클 때문에 단순한 이분 매칭 알고리즘을 사용할 수 없다. Edmonds의 blossom 알고리즘을 사용한다.

현재 매칭에 대한 증가 경로를 BFS로 찾는다. 탐색 도중 같은 BFS 트리에 속한 두 정점 사이의 간선을 만나 홀수 사이클이 만들어지면, 그 사이클 전체를 하나의 blossom으로 축약한다. 축약된 그래프에서 증가 경로를 계속 찾을 수 있으며, 증가 경로가 발견되면 부모 배열을 따라가며 매칭 여부를 뒤집는다.

구현에서는 각 정점이 현재 속한 blossom의 대표를 나타내는 $base$ 배열, BFS 부모를 나타내는 $p$ 배열, 현재 매칭 상대를 나타내는 $match$ 배열을 관리한다. 두 정점이 만드는 blossom의 최소 공통 조상은 매칭 간선과 BFS 부모 간선을 번갈아 따라가며 찾는다. blossom을 축약할 때는 사이클 위의 모든 대표를 최소 공통 조상으로 바꾸고, 새로 탐색 가능해진 정점을 BFS 큐에 넣는다.

증가 경로 하나를 찾을 때 $O(N^2)$ 시간이 들고, 매칭 크기는 최대 $\lfloor N/2 \rfloor$번 증가하므로 전체 시간 복잡도는 $O(N^3+M)$이다. 메모리 복잡도는 $O(N+M)$이다.

출력할 때는 $match[v]$가 존재하고 $v<match[v]$인 정점만 한 번씩 출력하면 된다.

Solution written by GPT5.6