原题
请找出有向图中弱联通分量的数目。图中的每个节点包含其邻居的 1 个标签和1 个列表。 （一个有向图中的相连节点指的是一个包含 2 个通过直接边沿路径相连的顶点的子图。）
样例
给定图:
A----->B C
\ | |
\ | |
\ | |
\ v v
->D E <- F
返回 {A,B,D}, {C,E,F}. 图中有 2 个相连要素，即{A,B,D} 和 {C,E,F} 。
解题思路
- 首先了解有向图中的一个概念
- 弱连通块 - 有向图中，A能到B，B不能到A
- 强连通块 - 有向图中，A能到B，B也能到A
- 本题是使用Union Find的典型题，Union Find(并查集)主要提供以下操作：
- Find - 判断在不在同一个集合中，边查找边路径压缩，均摊时间复杂度O(1)。
def compressed_find(self, x):
parent = father[x]
while parent != father[parent]:
parent = father[parent]
temp = -1;
fa = father[x]
while fa != father[fa]:
temp = father[fa]
father[fa] = parent
fa = temp
return parent
- Union - 合并两个集合，时间复杂度O(1)
- 遍历所有nodes建立hashset，初始化Union Find
- 遍历第二遍，合并每个node和他们neighbors的father
完整代码
# Definition for a directed graph node
# class DirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class UnionFind:
def __init__(self, hashset):
self.father = {}
for item in hashset:
self.father[item] = item
def find(self, x):
parent = self.father[x]
while parent != self.father[parent]:
parent = self.father[parent]
return parent
def compressed_find(self, x):
parent = self.father[x]
while parent != self.father[parent]:
parent = self.father[parent]
temp = -1;
fa = self.father[x]
while fa != self.father[fa]:
temp = self.father[fa]
self.father[fa] = parent
fa = temp
return parent
def union(self, x, y):
fa_x = self.find(x)
fa_y = self.find(y)
if fa_x != fa_y:
self.father[fa_x] = fa_y
class Solution:
# @param {DirectedGraphNode[]} nodes a array of directed graph node
# @return {int[][]} a connected set of a directed graph
def connectedSet2(self, nodes):
# Find all the different nodes in the Graph, store in the hashSet
myHashSet = set()
for node in nodes:
myHashSet.add(node.label)
for neighbor in node.neighbors:
myHashSet.add(neighbor.label)
# right now, one node's father is itself
unionFind = UnionFind(myHashSet)
for node in nodes:
node_father = unionFind.compressed_find(node.label)
for neighbor in node.neighbors:
neighbor_father = unionFind.compressed_find(neighbor.label)
if node_father != neighbor_father:
unionFind.union(neighbor.label, node.label)
# group the node with same father
resMap = {}
for node in nodes:
father = unionFind.compressed_find(node.label)
if father not in resMap:
resMap[father] = [node.label]
else:
if node.label not in resMap[father]:
resMap[father].append(node.label)
# append each group into the result
result = []
for key, value in resMap.iteritems():
result.append(value)
return result
