BOJ 3748 Lucky cities
문제 내용
정점의 개수가 이고 간선의 개수가 인 단순 무방향 무가중치 그래프가 주어집니다. 적어도 하나의 길이가 홀수인 단순 사이클에 포함되는 정점의 수를 구하세요.
입력
첫 줄에는 테스트 케이스의 수 가 주어집니다. ()
각 테스트 케이스에 대해, 첫 줄에는 과 의 값이 주어집니다. ()
다음 줄에는 서로 다른 두 정수 와 가 주어집니다. 이는 번 정점과 번 정점을 잇는 하나의 간선이 존재함을 의미합니다. ()
출력
각 테스트 케이스에 대해 문제의 정답을 한 줄에 출력합니다.
문제 풀이
스포일러
먼저, 그래프를 biconnected components로 나눕니다. 모든 단순 사이클은 하나의 BCC의 내부에서만 존재할 수 있습니다.
하나의 BCC가 이분 그래프라면 그 내부에는 홀수 사이클이 존재하지 않습니다. 그렇지 않다면 홀수 사이클이 적어도 하나 존재합니다. 이제 홀수 사이클이 적어도 하나 존재하면, 그 BCC 내의 모든 정점에 대해 그 정점을 포함하는 홀수 사이클 또한 찾을 수 있음을 증명합니다.
그 사이클의 밖에 있는 정점 를 생각해 보면, 그 정점에서 홀수 사이클 내의 서로 다른 정점 와 로 연결되는 vertex-disjoint한 두 개의 경로가 존재합니다. 와 로 홀수 사이클을 나누면 한쪽 경로는 길이가 짝수이고 반대쪽 경로는 홀수이므로, 경로 와 위의 간선의 수가 홀수이든 짝수이든 를 포함하는 홀수 사이클을 찾을 수 있습니다. (이 증명은 deuslovelt님의 기여 코멘트에서 가져왔습니다.)
따라서, 각 BCC가 이분 그래프인지 판별하고, 그렇지 않다면 그 BCC 내의 모든 정점을 답에 추가하여 마지막에 전체 정점의 수를 출력하면 됩니다. (단절점은 여러 개의 BCC에 포함될 수 있음에 주의합니다.)