79brue의 PS 블로그

문제 링크15685B+alpha를 짜고 풀었다. 지금까지 해본 다양한 문제풀이들 중에서도 기억에 남을 정도로 힘들었던 것 같다. 자력솔한 문제 중에서는 최소 3위 안에 드는 것 같다. 해싱을 쓰는 쉬운 풀이가 있다고 하니 구현할 생각이 있다면 그쪽 풀이를 써 보도록 하자. 문제를 요약하면 다음과 같다.그래프 $G$에서 간선 $k$개를 지워서 이분 그래프로 만들 수 있는 $k$의 최솟값 $k_{min}$이 $2$ 이하인지 판정한다.$k_{min}$이 $2$ 이하라면, 그래프 $G$에서 $k_{min}$개의 간선을 지워 이분 그래프로 만드는 경우의 수를 출력한다.접근 방식이 문제에서는 $k_{min}$이 $0$, $1$, $2$인지 각각에 대해서만 판정하면 된다. 따라서 $k_{min}$의 값이 이들 중에 ..