Submission #22109995

---

Source Code Expand

(N,M),*AB = $<.map{|ln| ln.split.map(&:to_i) }

E = [0]*(N+1)
AB.each{|a,b|
	E[a] |= 1<<b
	E[b] |= 1<<a
}

G = [-1]*(N+1)
F = lambda{|a|
	G[a]<0 ? a : G[a] = F[G[a]]
}
U = lambda{|ab|
	a,b = ab.map(&F)
	next if a==b
	a,b = b,a if G[b]<G[a]
	G[a] += G[b]
	G[b] = a
}
AB.each(&U)

V = (1..N).sort_by{|v| -E[v].to_s(2).count(?1) }.group_by(&F).values
S = lambda{|vs|
	(v0,e0), = vs = vs.map{|v| [1<<v,E[v]] }
	c0,c1,c2 = v0,0,0
	n0,n1,n2 = e0,0,0
	cnt = lambda{|i|
		next 1 unless (v,e = vs[i])
		next 0 if v <= n0&n1&n2
		s = 0
		c0,n0,_,_,s = c0,n0,(c0|=v),(n0|=e),s+cnt[i+1] if c0&e < 1
		c1,n1,_,_,s = c1,n1,(c1|=v),(n1|=e),s+cnt[i+1] if c1&e < 1
		c2,n2,_,_,s = c2,n2,(c2|=v),(n2|=e),s+cnt[i+1] if c2&e < 1
		next s
	}
	next 3*cnt[1]
}
p V.map(&S).inject:*

Submission Info

Judge Result