オレンジグラフの別解（TLEしました．）

昔昔にオレンジグラフという問題が出ていましたね． atcoder.jp

これはどういう問題かというと，グラフが与えられるので，極大な部分二部グラフ（これ以上二部性を保証しながら辺追加ができない部分二部グラフ）の列挙が想定解法なのですが，計算時間が $O(m 2^n)$ 時間と指数的に時間がかかります．

列挙アルゴリズムではこのように指数時間かかるのはそもそも答えの数が指数個あるので，ある種しょうがないのですが，この答えの個数というバウンドを使ってしまうと面白みがなくなる問題もいろいろあります．例えば，線分の集合が与えられた時に，その交点を列挙しろという問題では，$n$を線分の個数とすると，ナイーブアルゴリズムは $O(n^2)$ 時間で動作します．しかも，最悪時，交点の個数は $O(n^2)$ なので，このナイーブアルゴリズムが最適になってしまいます．なんかこれでは面白くないということで，答えの個数を$M^{}$とおき，$M^{}$と$n$を使って計算量を見積もるというアルゴリズムが開発されてきました．交点列挙なら，確か $O( ( n+M ) \log n)$で列挙できたと思います（自信ない）．このように解の個数と入力サイズの2つを用いて計算量が抑えられるアルゴリズムを出力依存型アルゴリズム（Output sensitive algorithm）と言います．

ここで自然な疑問として，今回のオレンジグラフもOutput sensitiveに解けないのか？という疑問があります．実はこれは解くことができます！具体的には今回実装したアルゴリズムは $O(M m^2)$ 時間，$O(M m)$領域のアルゴリズムになっています．ちなみに本当のことを言うと実装をサボるために時間が$O(M m^2 \alpha(2n, n) )$ 時間になっています． $\alpha(2n, n)$ はいつも通りunion findの計算量です．noshi91さん，実装のアドバイスありがとうございました！．

noshi91.hatenablog.com

正当性の証明は結構めんどくさいのですが，アルゴリズムはめっちゃ簡単です．正当性に関する解説はここですね．

qiita.com

ざっくり証明のアイディアを説明すると，こんな感じです．基本的に，極大部分二部グラフ（MB）から別のMBを作るのはそんなに難しくなく，たくさん答えを見つけることはできます．具体的にはあるMBを1つ見つけてから，そのMBに含まれない辺1つからなる部分グラフは二部グラフなので，それに適当に辺を追加し，MBを作れば別なMBを作ることができます．なので，問題は全てのMBを出力できているかです．これを証明するためには，MBとMBの間に距離のような指標を定義してあげるというアイディアが結構うまくいきます．これは何をしたいかというと，MBを1つの頂点だと思い，MBから別のMBを作るルールを有向辺だと思った時にできるグラフを強連結にしたいという思想から来ています．もしこのルールで作られたグラフが強連結なら，適当にBFSやDFSすればMBが列挙できますね．ここで，強連結の定義を思い出すと，「任意の頂点ペア $u$ と $v$ について $u$-$v$ パスが存在する」でしたね．このパスの存在性を示すために， $u$ から $v$ に到達可能であることを示す必要があります．そのため， 今のMBから別のMB'に到達可能ということを示すため，MBとMB'の間にある指標を定義し，その指標を小さく or 大きくするMBに到達できるということを示すというのが一つの戦略になります．いろいろ言いましたが，最後に結論だけ言ってしまうと，MBの頂点ID最小の頂点からBFS順に辺を並べて，その辺の列のprefixをどんどん伸ばしていくということをやっていけば必ず欲しい解MB'に到達できるよ〜というお話しです．以上が証明の気分でした．

具体的なアルゴリズムは以下のとおりです．

• 適当にMBを求める．
• 得られたMBをキューに突っ込み，キューが空になるまで以下を繰り返す．
  • キューからMBを一つ取り出す．
  • MBに含まれない辺$e = \set{x, y}$を選択し，MBから$x$に接続した辺を全て削除して得られるMBxと$y$に接続する辺を全て削除して得られるMByを作る．
  • MBxとMByに適当に辺を追加して極大な二部グラフを作る．得られた極大二部グラフがまだ出力していない解ならば，キューに突っ込む．

というわけで意気揚々とAtCoderさんに投げたのですが，TLEしました！（悲しいね）．僕が思ったより答えの数が多かったようで，多項式倍の部分で勝てなかったようです．．． 結構このアルゴリズムの実装は楽チンで，union find partとデータの受け取りとか除くと大体50行くらいでかける感じでした．

以下ソースコードです．

#include<iostream>
#include<queue>
#include<set>
class edge{
public:
    int x, y;
};
class UnionFind{
public:
  UnionFind();
  UnionFind(int _n){init(_n);}
  void init(int _n){
    n = _n;
    if(rank.size() == 0)rank.resize(n), parent.resize(n);
      for (int i = 0; i < n; i++) {
      rank[i] = 0;
      parent[i] = i;
    }
  }
  int find(int x){
    if(x == parent[x])return x;
    else return parent[x] = find(parent[x]);
  }
  
  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    if(rank[x] < rank[y]){
      parent[x] = y;
    }else{
      parent[y] = x;
      if(rank[x] == rank[y])rank[x]++;
    }
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }
  int size(){
    int res = 0;
    for (int i = 0; i < n; i++) {
      if(parent[i] == i)res++;
    }
    return res;
  }
private:
  int n;
  std::vector<int> rank, parent;
};

UnionFind uf(40);
 
std::vector<int> Maximize(std::vector<edge> &G, int n, std::vector<int> &subg){
    uf.init(2*n);
    for(int i = 0; i < (int)G.size(); i++) {
      int x = G[i].x, y = G[i].y;
      if(subg[i] == 1) uf.unite(x+n, y), uf.unite(x, y+n);
    }
    for(int i = 0; i < (int)G.size(); i++) {
      int x = G[i].x, y = G[i].y;
      if(subg[i] == 0){
          subg[i] = 1;
          if(not uf.same(x+n, y+n)) uf.unite(x+n, y), uf.unite(x, y+n);
          else subg[i] = 0;
      }
  }
  return subg;
}
 
void EnumerateNeighborhoods(std::vector<edge> &G, std::vector<int> &subg, int a, int n, std::set<std::vector<int> > &ans, std::queue<std::vector<int> > &que){
    std::vector<int> S = subg;
    for(int i = 0; i < (int)G.size(); i++) {
        if(G[i].x == G[a].x or G[i].y == G[a].x)S[i] = 0;
    }
    S[a] = 1;    
    Maximize(G, n, S);
    if(ans.find(S) == ans.end()){
        ans.insert(S);
        que.push(S);
    }
 
    S = subg;
    for(int i = 0; i < (int)G.size(); i++) {
        if(G[i].x == G[a].y or G[i].y == G[a].y)S[i] = 0;
    }
    S[a] = 1;
    Maximize(G, n, S);
    if(ans.find(S) == ans.end()){
        ans.insert(S);
        que.push(S);
    }
}
 
int main(){
    int n, m;
    std::cin >> n >> m;    
    std::vector<edge> G(m);
    std::set<std::vector<int> > ans;
    for(int i = 0; i < m; i++) {
        int from, to;
        std::cin >> from >> to;
        G[i].x = --from, G[i].y = --to;
    }
    std::vector<int> subg(m, 0);
    Maximize(G, n, subg);
    std::queue<std::vector<int> > que;
    que.push(subg);
    ans.insert(subg);
    while(not que.empty()){
        subg = que.front();
        que.pop();
        for(int i = 0; i < m; i++) if(subg[i] == 0) EnumerateNeighborhoods(G, subg, i, n, ans, que);
    }
    std::cout << ans.size() << std::endl;
}