매칭이란, 정점이 겹치지 않도록 간선을 고르는 것을 뜻한다. 즉, 정점 하나당 최대 하나의 매칭된 간선에 연결되어 있을 수 있다. 그 중에서도 매칭된 간선의 개수를 최대화하는 문제를 최대 매칭이라고 부른다.

여러분은 아마 이분 그래프에서의 최대 매칭은 한번쯤 풀어봤을 것이다.

일반 그래프에서의 최대 매칭은 Blossom Algorithm이라는 것을 통해 구할 수 있지만, 이해하기도 어렵고 구현하기는 더 어렵다.

이번에는 거의 일반 그래프에서 매칭 문제를 풀 것이다. 거의 일반 그래프란, 정점 번호의 차이가 A 또는 B인 간선만 존재하는 그래프이다. 구체적으로 Ui와 Vi(Ui<Vi)를 잇는 간선이 있다면, Vi-Ui=A이거나 Vi-Ui=B이다.

하지만 이렇게 문제를 낸다면 아마 인터넷에서 Blossom Algorithm을 복붙하는 친구들이 있을 것 같아, 최대 매칭 대신 매칭의 개수를 구해보도록 한다.

주어진 거의 일반 그래프에서 매칭의 개수를 구하여라. 최대 매칭이 아니어도 됨에 유의하라.

거의 일반 그래프 매칭 timer 5s memory 1024MB

거의 일반 그래프 매칭 5s 1024MB