Um_nik의 알고리즘
시간 제한4초메모리 제한512 MB
정점 2e6, 간선 2e6 규모의 이분 그래프가 주어질 때, 최대 매칭 크기의 0.95배 이상인 매칭을 찾아 출력하는 문제로, 상수 최적화가 필수적이다.
문제
내 학사 논문을 5시간 안에 재현할 수 있겠는가?
무향 이분 그래프가 주어진다. 이 그래프의 최대 매칭 크기를 K라고 하자. 크기가 적어도 0.95 · K인 매칭을 찾는 알고리즘을 고안하라.
Accepted를 받고 싶다면, 코드를 최대한 최적화하는 것을 권장한다.
입력
첫째 줄에 세 양의 정수 n1, n2, m (1 ≤ n1, n2, m ≤ 2 · 10^6)이 주어진다. 이는 각각 첫 번째 파트의 정점 수, 두 번째 파트의 정점 수, 그래프의 간선 수이다.
다음 m개의 줄에 간선이 한 줄에 하나씩 주어진다. 각 간선은 두 정수 u, v (1 ≤ u ≤ n1, 1 ≤ v ≤ n2)로 주어지며, 간선이 연결하는 첫 번째 파트와 두 번째 파트의 정점 id이다. 같은 두 정점을 연결하는 간선 쌍은 없다.
출력
첫째 줄에 찾은 매칭의 크기 L을 출력한다. 부등식 0.95 · K ≤ L이 성립해야 한다.
다음 L개의 줄에 매칭에 포함된 간선의 번호를 출력한다. 간선은 입력에 주어진 순서대로 1부터 m까지 번호가 매겨진다.