홀수 차수 그래프

서브태스크 1: 가능한 $\binom{N}{2}$개 간선의 모든 부분집합을 열거한다. 각 그래프의 간선 수, 연결성, 홀수 차수 정점 수를 검사한다. 시간 복잡도는 $O(2^{\binom{N}{2}}N^2)$, 공간 복잡도는 $O(N^2)$이다.

전체 풀이: 모든 정점의 차수의 합은 간선 수의 두 배이므로 짝수이다. 따라서 홀수 차수 정점의 수 $K$가 홀수이면 불가능하다. $N=1$이면 $K=1$이므로 이 경우도 자동으로 처리된다.

$K$가 짝수이면 $K\geq2$이다. 먼저 정점 $1$과 각 정점 $2,3,\ldots,K$를 잇는다. 중심 $1$의 차수는 로 홀수이고, 나머지 개 정점의 차수는 이므로 홀수 차수 정점이 정확히 개이다.

남은 정점은 $K$번 정점에서 시작하는 경로로 붙인다. 즉, $(K,K+1),(K+1,K+2),\ldots,(N-1,N)$을 추가한다. 정점을 하나 붙일 때마다 기존 경로 끝점의 차수가 에서 로 바뀌고 새 끝점의 차수는 이 되므로 홀수 차수 정점 수는 유지된다.

결과는 자기 루프와 중복 간선이 없는 연결된 트리이다. 간선 수는 $(K-1)+(N-K)=N-1$이므로 출력 제한도 만족한다. $K=N$이면 경로를 추가하지 않는다.

케이스당 시간 복잡도는 $O(N)$, 출력 버퍼를 제외한 추가 공간 복잡도는 $O(1)$이다. 채점기는 중복 간선을 집합으로 검사하고 서로소 집합 자료구조로 연결성을 검사하여 $O(N+M\log(M+1))$ 시간과 공간을 사용한다. 이며 모든 계산은 64비트 부호 있는 정수 범위 안에 있다.

Solution written by GPT