$C_4$ Find Algorithm

コードについての説明

無向グラフ $G$ に長さ $4$ の単純閉路が含まれるかどうかを返すアルゴリズム.
各点 $u$ について $u$ を端点とする無向辺で $(u,v)$, $(u,w)$ というものが存在した場合 $check[v][w]$, $check[w][v]$ を true にする. 別の頂点について見ているときにすでに check に true がすでに入っていたなら長さ $4$ の単純閉路が存在することになる. check 配列の同じ部分を二度参照すると即座に true が返されるので計算量は $\O (n^2)$
(補足) ちなみに $\O \left( m^{1.5} \right)$ 時間で $C_4$ の finding だけでなく counting も行うアルゴリズムが存在し, 疎グラフの場合はこちらの方が高速である.(参考).

時間計算量: $\O (n^2)$

コード

bool C4_Find(vector<vector<int> >& G) {
    int n = (int)G.size();
    vector<vector<bool> > check(n, vector<bool>(n, false));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < (int)G[i].size()-1; j++){
            for(int k = j+1; k < (int)G[i].size(); k++){
                if(check[G[i][j]][G[i][k]]) return true;
                check[G[i][j]][G[i][k]] = check[G[i][k]][G[i][j]] = true;
            }
        }
    }
    return false;
}

verify 用の問題

verify していません(verify 問題を知らない)