分离无连接子图 The problem is, given a set of edges(node, node), seperate all subgraphs that are isolated from each other. Isolation of two graphs Gx and Gy is defined as every node Xi in Gx has no edge(or path) to every node Yi in Gy.

data = [[1,2],[2,3],[3,4],[5,6],[6,7]]
# expect output 2 subgraph of {1,2,3,4} and {5,6,7}

naive idea, construct a set of nodes of a subgraph, a new node is added to the set if it can connect to any node in the set

def getSubgraphs(data):
rstList = []
for row in data:
connect = False
for s in rstList:
if row in s or row in s:
s.update(row)
connect = True
break
if not connect:
rstList.append(set(row))
return rstList

rstList = getSubgraphs(data)
print rstList

[set([1, 2, 3, 4]), set([5, 6, 7])]

data.append([4,5])
# this edge should connect two subgraph

rstList = getSubgraphs(data)
print rstList

[set([1, 2, 3, 4, 5]), set([5, 6, 7])]

Not as expected, something must be wrong!

Later added edges may connect preview added sets together, check every pair of sets to see if they have any intersection

import itertools
def combineSet(rstList):
for a,b in itertools.product(rstList, repeat=2):
if a<>b and len(a&b) > 0:
rstList.remove(a)
rstList.remove(b)
rstList.append(a|b)
break

iterate to combine sets till length of list don’t change

while True:
length = len(rstList)
combineSet(rstList)
if length==len(rstList):
break
print rstList

[set([1, 2, 3, 4, 5, 6, 7])]

If you are familiar with Leetcode, you may feel like it is a real world practice of Merge Intervals.