[BOJ] 1017

소수 쌍

1017번 https://www.acmicpc.net/problem/1017

이분매칭을 이용하는 문제입니다.

정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는
형태의 그래프를 이분 그래프(bipartite graph)라고 합니다.
한쪽 그룹을 A, 다른 쪽 그룹을 B 라고 하고, 각 그룹의 각 정점이 원하는 항목이 정해져 있을 때
최대 매칭을 찾아내는 것을 이분매칭이라고 합니다.

우리는 합이 소수가 되는 두 수의 쌍을 찾아야 하므로
홀수와 짝수 두 개의 그룹으로 나눠서 이분 매칭을 진행할 수 있습니다.

이분 매칭을 진행했을 때 첫번째 수와 매칭될 수 있는 모든 수를 찾아야 하므로
이분 매칭을 통해 모든 수들을 쌍을 지었을 때마다
첫번째 수와 첫번째 수와 매칭된 수를 잇는 간선을 지우면서 이분매칭을 진행해주면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1017.cpp