便宜上、グラフを\(G\)、次数列を\(d\)により表します。

\(G\)から\(d\)を生成するとき、重複するのは\(G\)のサイクルの向きの自由度の分なので、全てのサイクルがある片方の向きを向いているという条件を満たす\(G\)と\(d\)は一対一対応します。

よって、ここで包除原理を適用し、指定したサイクルについて逆向きのサイクルを作り、残りは自由に決めるという数え上げに帰着することにより、\(O(N)\)でdpにより答えを求めることができます。