Submission #1100279

---

Source Code Expand

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

G = {}
V = n.times.to_a
E = m.times.map { gets.split.map{|v| v.to_i - 1} }

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

Submission Info

Judge Result