奇数次数のグラフ

サブタスク 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