順番は無関係なのでで固定して赤黒木のような感じでDFSする。白線では遷移自体はせず赤線で遷移する。完全グラフの完全マッチングは「残った頂点のうち最も小さい番号の頂点に対して相手を選ぶ」を繰り返すことで数え上げることが出来る。残った頂点のうち最も小さい番号を選ぶのは1通り、最も小さい番号の相手は（既にk個の頂点を選んでいたとして）n-k-1通り。計算量は
https://atcoder.jp/contests/abc318/submissions/51000950
今までC(n,2)の総積だと思っていてngtkanaさんに数え方を教えてもらった。
なるほどです。C(n, 2) ・…… という式も筋は良いのですが、これでは組に番号がついてしまいます。「今残っている中で一番若い頂点の相方」が何通りかを考えると二重階乗がスッと納得できるかもです。
— ながたかな@VSinger (@ngtkana) December 14, 2023
例えば、下図の競争の順位を決めるときは4×3×2通り。掛け算での数え上げには番号や順位を決めるという意味があって、完全グラフの完全マッチングではA-B-CとC-B-Aを同じカウントにしなければならない。
