最大クリーク問題　試行 - 高温処理済みコースケ

いままでと全然変えてみてある辺(i,j)を含む、順序上 j以下の頂点で構築できる最大クリークとか考えてみた。
サイズcのクリークがある時、全点から接続している点はc+1のクリークって考えると凄くコンパクト。

でも2^cとか含むだろうけどね。

n,m = gets.split.map(&:to_i)
G = {}
U = {}
V = n.times.to_a
E = m.times.map do
    gets.split.map(&:to_i).sort
end
E.sort!

V.each do |v| 
   G[v] = []
   U[v] = [] 
end
E.each do |from, to| 
    G[from] << to
    G[to] << from
    U[to] << from
end

MEMO = {}

def dfs(clique, c)
    clique.sort!
    s,t = clique.first, clique.last
    status = clique.join(' ')
    return MEMO[status] if MEMO[status]
    
    nclique = clique.inject(U[t]){|n, v| n & G[v] }.sort
    nc = nclique.empty? ? c : nclique.map {|nv| dfs(clique + [nv], c+1) }.max
    p clique: clique, c: nc
    MEMO[status] = nc
end

E.each do |e|
    puts "#{e} #{dfs(e, 2)}"
end

なんとなくこのコードが引っかかる。

再帰呼び出しc回でサイズcの極大クリークが見つかる、サイズcのクリークは2^c - 1個のクリークがあるけど、なんとなくうまく枝刈りするとサイズがcの極大クリーク(他のクリークに含まれないの意味)をc^2のオーダーで抜けれそうな気がするんだよね。

例えばこんな感じのコードかなぁ。

n,m = gets.split.map(&:to_i)
VISITED = {}

G = {}
V = n.times.to_a
E = m.times.map { gets.split.map(&:to_i).sort }

V.each {|v| G[v] = [] }
E.each do |from, to|
    G[from] << to
    G[to] << from
end

def dfs(clique, max)
    clique.sort!
    status = clique.join(' ')
    
    return max if VISITED[status]
    
    VISITED[status] = true
    
    if clique.size > max
        max = clique.size
        # p clique: clique, max: max
    end
    
    head, *body = clique
    nclique = body.inject(G[head]){|n, v| n & G[v] }
    if clique.size + nclique.size > max
        max = nclique.inject(max) {|m, u| dfs(clique + [u], m) } 
    end
    
    max
end

if n == 0
    puts 0
elsif m == 0
    puts 1
else
    puts E.inject(0){|max, e| dfs(e, max) }
end

下記入力に対して

こういう動き

{:clique=>[0, 1], :max=>2}
{:clique=>[0, 1, 2], :max=>3}
{:clique=>[0, 1, 2, 3], :max=>4}
{:clique=>[0, 1, 3], :max=>4}
{:clique=>[0, 2], :max=>4}
{:clique=>[0, 3], :max=>4}
{:clique=>[1, 2], :max=>4}
{:clique=>[1, 3], :max=>4}
{:clique=>[2, 3], :max=>4}
{:clique=>[0, 4], :max=>4}
{:clique=>[0, 5], :max=>4}
{:clique=>[0, 6], :max=>4}
{:clique=>[0, 7], :max=>4}
{:clique=>[4, 7], :max=>4}
{:clique=>[4, 5], :max=>4}
{:clique=>[5, 6], :max=>4}
{:clique=>[6, 7], :max=>4}

サイズcのクリークの全点から接続している点は必ずサイズc+1のクリークで、これまでに見つかった最大クリークのサイズをmaxとすると、サイズc+1のクリークがmax - c個より多く存在しないとmax + 1のサイズのクリークはないので枝刈ってみた。

Submission #1100279 - AtCoder Beginner Contest 002 | AtCoderの結果

これcarraghanのアルゴリズムっぽい。。。
https://www.jstage.jst.go.jp/article/ciqs/2006/0/2006_0_JP04/_pdf