ある確率(3) - inamori’s diary

これの続き

1. まず、次数0の点があれば
それは明らかにダメ

2. 次数1の点があれば
それは男のほうだが、
その男はペアとなるべき女が決まるので、
その男と女はグラフから取り除く。
このとき女は次数2だから辺が2つ減る。

3. 次数が全て2以上なら
次数は全て2である。
それは1つまたは複数閉路になるから、マッチする。

2を繰り返して、
1になればマッチしない、3になればマッチする。

でも、これは今回の問題に限った手法で
（両方が同じ点の数で、一方が全て次数2）、
本当は2部グラフ全般の判定法がほしい気がする。

判定のとき、グラフを

64ビット符号無し整数→（点→隣接点の集合）のマップ

と表現を変える。
C++/STLなら次のよう。

  map >

こうすると上の操作がしやすくなる。
例えば次数は、

  map >::iterator p;
  p->second.size();

と表せる。
でも非常に遅そう。
本当はグラフを操作するクラスでも作ればいいんだろうけど。

あと、確率ではなく場合の数で。
32ビット符号無し整数で収まりそうだからそっちで。

3764057850/13492928512（≒0.278965）

擬似乱数を用いて100万回シミュレーションしたときも
だいたいそんな感じだったと思うので。

最後のはおととい歩いている間ずっと考えてたんだけど、
う〜ん、難しい。
まず、連結部に分けて、そのあとが問題。
長い閉路を見つける。
でも長さが同じだったらどうするんだろう、とか。

これができたらもっとメモリが少なくてすみそうなのに。