Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Break Rings by Moff
from collections import defaultdict
import itertools
class Graph(object):
def __init__(self):
self.adjacent = defaultdict(list)
self.vertices = set()
def add_edge(self, v1, v2):
self.adjacent[v1].append(v2)
self.adjacent[v2].append(v1)
self.vertices.add(v1)
self.vertices.add(v2)
def is_independent_subset(self, subset):
for v in subset:
for w in self.adjacent[v]:
if w in subset:
return False
return True
def break_rings(connections):
g = Graph()
for v1, v2 in connections:
g.add_edge(v1, v2)
n = len(g.vertices)
for i in range(1, n):
for c in itertools.combinations(g.vertices, n-i):
if g.is_independent_subset(c):
return i
return 0
July 23, 2015
