Submission #1271432

---

Source Code Expand

class Graph
  
  attr_reader :vertices
  attr_reader :edges
    
  def initialize(vset, eset)
    @vertices = vset
    @edges = eset
    @graph = build_graph(vertices, edges)
  end
  
  def inspect
    "<Graph: n = #{vertices.size}, m = #{edges.size} #{vertices.inspect}>"
  end
 
  def empty?
    vertices.empty?
  end
  
  def degree(v)
    @graph[v].size
  end
 
  def super_clique_vertices(e)
    u,v = E[e]
    @graph[u] & @graph[v]
  end
  
  def count_cliques(e)
    super_clique_vertices(e).size + 2
  end
  
  def induced_subgraph(vset, w_limit = 0)
    use = {}
    vset.each{|v| use[v] = true }
    eset = edges.select{|e| E[e].all?{|v| use[v]} }
    Graph.new(vset, eset)
  end
 
  def build_graph(vset, eset)
    hash = {}
    vset.each {|v| hash[v] = [] }
    eset.each do |e| 
      u,v = E[e]
      hash[v] << u
      hash[u] << v
    end
    hash
  end
 
  def compact!(c, w_limit = 0)
    loop do
      esize = edges.size
      
      vset = vertices.select {|v| degree(v) >= c - 1 }
      use = {}
      vset.each {|v| use[v] = true }
      eset = edges.select{|e| E[e].all?{|v| use[v]} }
 
      @vertices = vset
      @edges = eset
      @graph = build_graph(vset, eset)
      
      break if esize - edges.size == 0
    end
    self
  end
 
  def delete_edge(e)
    u,v = E[e]
    @graph[v].delete(u)
    @graph[u].delete(v)
  end
 
  def max_clique
    
    highest_clique_size = E.size > 0 ? W[edges.first] + 1 : 1
    max_clique = []
 
    # Probably Dinkelback algorithm. 
    (1 .. highest_clique_size).find do |c|
      next if max_clique.size >= c
      clique = contain_clique?(c) # After evaluation, it can restart edge which found this clique.
      if clique
        # puts "#{"%3d" % c} #{clique.sort.map{|v| "%3d" % v }.join(' ')}"
        max_clique = clique 
      end
      !clique
    end
    max_clique
  end
  
  def contain_clique?(c, w_limit = c)
 
    return [] if c <= 0
 
    return vertices.size > 0 ? [vertices.first] : false if c == 1
 
    return edges.size > 0 ? E[edges.first] : false if c == 2
 
    return false if c > vertices.size
 
    return false if c * (c - 1) > edges.size * 2
 
    compact!(c, w_limit)
    
    vsize = vertices.size
    a = vertices.select{|v| degree(v) == vsize - 1}
 
    return a if a.size >= c
      
    if a.size > 0
      g = induced_subgraph(vertices - a, w_limit)
      clique = g.contain_clique?(c - a.size, w_limit)
 
      return a + clique if clique
 
    else
      esize_limit = c * (c - 1) / 2
      until edges.empty?
        break if edges.size < esize_limit || W[edges[esize_limit - 1]] < w_limit
        e = edges.shift
        vset_e = super_clique_vertices(e)
        
        break if W[e] < c
        
        if vset_e.size >= c - 2
 
          subgraph = induced_subgraph(vset_e, w_limit)
          clique = subgraph.contain_clique?(c - 2, w_limit)
 
          if clique
            edges.unshift(e) # push front last edge for max_clique restart at this e.
            return clique + E[e] 
          end
          
        end
 
        delete_edge(e)
 
        if E[e].any?{|v| degree(v) < c - 1 }
          compact!(c)
        end
        
      end
    end
    return false
  end
end
 
 
n, m = gets.split.map(&:to_i)
V = (1 .. n).to_a
E = m.times.map { gets.split.map(&:to_i).sort.freeze }.freeze
G = Graph.new(V, m.times.to_a)
 
W = Array.new(m, n)
E.each_index {|e|  W[e] = G.count_cliques(e) }
 
G.edges.sort_by!{|e|  -W[e] }
 
puts G.max_clique.size

Submission Info

Judge Result