In graph theory, a connected component (or justcomponent) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
Connected Components即连通域，适用于无向图。一个连通域，指的是这里面的任意两个顶点，都能找到一个path连通。
连通域问题偶尔也会遇到，好在这种题一般用常规做法计数连通域个数就可以了。下面详细介绍这个做法：
class UnionFind(object):
def __init__(self, n):
self.set = list(range(n))
self.count = n
def find_set(self, x):
if self.set[x] != x:
self.set[x] = self.find_set(self.set[x]) # path compression.
return self.set[x]
def union_set(self, x, y):
x_root, y_root = map(self.find_set, (x, y))
if x_root != y_root:
self.set[min(x_root, y_root)] = max(x_root, y_root)
self.count -= 1
class Solution(object):
def countComponents(self, n, edges):
"""
:type n: int
:type edges:List[List[int]]
:rtype: int
"""
union_find = UnionFind(n)
for i, j in edges:
union_find.union_set(i, j)
return union_find.count
首先，数据类型是[node1, node2]的edge的list，node的值代表其序号，从0到n-1；其次，算法的核心思想，就是把连在一起的节点的root值设置成为一样。为了实现这个目的，算法把一个连通域里面的所有点的root设置成为最大节点的序号。
然后，值得注意的就是路径压缩了。因为连接有先后顺序，比如1连2，2连3，那么1其实也连着3，如何更新1的root值呢？就是通过这个find_set函数，意思是root值找下标，而不是具体的某个写定的数。这样，1看2的root，2看3的root，3最大，root就是它自己，因此1最后也能看到3的root。而假如3再和更大的数相连而改变root值，没关系，1照样能一路找过来。
时间复杂度是O（nlgn），空间复杂度是O（n）。
例1.Graph Valid Tree。给出n个节点，序号从0~n-1，以及一个edge的list，表示一个无向图，且edge不会重复，即假如已经有[0,1]就不会再有[1，0]。返回这个图是不是一棵树。
【解】其实这道题是在问两个问题：有没有环？是不是一整个连通域？
环很好解决，假设V个节点，E条边，没有环的话E=V-1，否则E>=V。
至于连通域，就用上面的方法可以做：
class UnionFind(object):
def __init__(self, n):
self.set = list(range(n))
self.count = n
def find_set(self, x):
if self.set[x] != x:
self.set[x] = self.find_set(self.set[x]) # path compression.
return self.set[x]
def union_set(self, x, y):
x_root, y_root = map(self.find_set, (x, y))
if x_root != y_root:
self.set[min(x_root, y_root)] = max(x_root, y_root)
self.count -= 1
class Solution:
# @param {int} n an integer
# @param {int[][]} edges a list of undirected edges
# @return {boolean} true if it's a valid tree, or false
def validTree(self, n, edges):
# Write your code here
if len(edges) != n - 1: # Check number of edges.
return False
elif n == 1:
return True
union_find = UnionFind(n)
for i, j in edges:
union_find.union_set(i, j)
return union_find.count == 1
时间和空间复杂度，和之前是一样的。
2.Number of islands。海岛个数。有一个mxn的全0矩阵，表示一片海，现在给出一个二维坐标list，代表按照顺序把对应的坐标置1，返回每一步操作之后海岛的数目。所谓海岛，就是通过上下左右相连的都是1的整个部分。比如给出n=m=3，和操作[[0,0],[0,1],[2,2],[2,1]]，返回[1,1,2,2]。（斜对角不算相连，不会对已经是1的坐标进行操作，不会给出无效坐标）。
【解】本质上还是求连通域的个数。
首先进行图的转换，因为要求序号在0~num-1，mxn矩阵总共有m*n个节点，因此每个节点的序号可以用行列数来决定，即row*n+col，序号从0到m*n-1。
然后每一步，看看周围有没有存在的连通域，这里需要考虑多个域在一个节点汇聚的情况，一个个都要merge，所以要依次遍历上下左右。merge只需要把两个点merge一下，路径压缩会自动把它们的root导到一起。因为序号都是不重复的，所以假如碰到下一个连通域，照样merge。代码如下：
# Time: O(klog*k) ~= O(k), k is the length of the positions
# Space: O(k)
class Solution(object):
def numIslands2(self, m, n, positions):
"""
:type m: int
:type n: int
:type positions: List[List[int]]
:rtype: List[int]
"""
def node_id(node, n):
return node[0] * n + node[1]
def find_set(x):
if set[x] != x:
set[x] =find_set(set[x]) # path compression.
return set[x]
def union_set(x, y):
x_root, y_root = find_set(x), find_set(y)
set[min(x_root, y_root)] = max(x_root, y_root)
numbers= []
number = 0
directions= [(0, -1), (0, 1), (-1, 0), (1, 0)]
set = {}
for position in positions:
node = (position[0], position[1])
set[node_id(node, n)] = node_id(node, n)
number += 1
for d in directions:
neighbor = (position[0] + d[0], position[1] + d[1])
if 0 <= neighbor[0] < m and 0 <= neighbor[1] < n and \
node_id(neighbor, n) in set:
if find_set(node_id(node, n)) !=find_set(node_id(neighbor, n)):
# Merge different islands, amortised time: O(log*k) ~= O(1)
union_set(node_id(node, n), node_id(neighbor, n))
number -= 1
numbers.append(number)
return numbers
