簡単なところから。
STLは遅いので、クラスを作って使いやすく、速くする。
基本的には、2部グラフの2つの点集合の点をそれぞれ0,1,2,…として、辺でつながっていたら、その辺の両端を行番号と列番号とする要素を1とする行列で表現する。
2部グラフは、
bipartite graph
と呼ぶので、こう名前をつけた。
2つの点集合の大きさが、NとM。
2がついているのは点集合の大きさMのほう。
neighborは隣の点でj番目のもの。
deletevertexは関連する辺も消える。
class BPGraph { int a[N][M]; int degree[N]; bool existvertex[N]; int degree2[M]; bool existvertex2[M]; public: BPGraph(); BPGraph(CODE c); int size(int i) const; int size2(int i) const; bool isexist(int i) const; bool isexist2(int i) const; int getelement(int i, int j) const; int neighbor(int i, int k) const; int neighbor2(int i, int k) const; void addvertex(int i); void addvertex2(int i); void deletevertex(int i); void deletevertex2(int i); void addedge(int i, int j); void deleteedge(int i, int j); };
こういうクラスを作ったら、マッチングの判定が63倍速くなった。