BOJ 28102 - 단순한 그래프와 이상한 쿼리
$K$가 홀수면 항상 가능하다.
왜냐면 $K$ 의 배수중 짝수도 있어서 큰 홀수, 큰 짝수 모두 만들 수 있어서 어떻게든 왔다갔다하기 방법으로 그만큼을 채울 수 있기 때문이다.
그래프에 홀수 길이의 싸이클이 있으면 항상 가능하다.
경로의 기우성을 자유롭게 조작할 수 있기 때문이다.
그래프에 홀수 길이의 싸이클이 없고 $K$가 짝수라고 해보자.
그럼 경로의 기우성을 바꾸는 것이 불가능하고 $a, b$ 까지의 거리가 짝수일 때만 가능하다.
이걸 판별하는 방법은 그래프를 이분그래프로 나누고 $a, b$의 색이 동일한지 검사하는 것이다.
Comments