시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 82 | 43 | 23 | 50.000% |
N개의 정점과 M개의 무방향 간선으로 이루어진 그래프가 입력으로 주어질 때에, 해당 그래프에서 최대 매칭의 크기를 출력하는 프로그램을 작성하시오.
그래프 G = (V, E)(|V|=N, |E|=M)에서 매칭 T는 E의 부분 집합이며, T의 어떠한 두 원소가 같은 정점을 공유해서는 안 된다.
최대 매칭이란 그러한 매칭 중 집합의 크기가 가장 큰 것을 이르는 말이다.
첫째 줄에 정점의 수를 나타내는 N(1≤N≤500)과 간선의 개수를 나타내는 M(1≤M≤124750)이 주어진다.
둘째 줄부터 M개의 줄에 걸쳐서 각 간선의 정보가 주어진다.
각 간선의 정보는 해당 간선을 이루는 서로 다른 두 정점의 번호로 구성된다.
각 정점의 번호는 1 이상 N 이하의 자연수이다.
두 정점 사이에 간선은 최대 1개임이 보장된다.
첫째 줄에 최대 매칭의 크기를 출력한다.
10 20 9 2 7 6 10 8 3 9 1 10 7 1 10 9 8 6 8 2 8 1 3 1 7 5 4 7 5 9 7 8 10 4 9 1 4 8 6 3 2 5
5
5 4 1 5 4 2 2 1 4 3
2