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即連通域，適用于無向圖。一個連通域，指的是這里面的任意兩個頂點(diǎn)，都能找到一個path連通。
連通域問題偶爾也會遇到，好在這種題一般用常規(guī)做法計(jì)數(shù)連通域個數(shù)就可以了。下面詳細(xì)介紹這個做法：
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
首先，數(shù)據(jù)類型是[node1, node2]的edge的list，node的值代表其序號，從0到n-1；其次，算法的核心思想，就是把連在一起的節(jié)點(diǎn)的root值設(shè)置成為一樣。為了實(shí)現(xiàn)這個目的，算法把一個連通域里面的所有點(diǎn)的root設(shè)置成為最大節(jié)點(diǎn)的序號。
然后，值得注意的就是路徑壓縮了。因?yàn)檫B接有先后順序，比如1連2，2連3，那么1其實(shí)也連著3，如何更新1的root值呢？就是通過這個find_set函數(shù)，意思是root值找下標(biāo)，而不是具體的某個寫定的數(shù)。這樣，1看2的root，2看3的root，3最大，root就是它自己，因此1最后也能看到3的root。而假如3再和更大的數(shù)相連而改變r(jià)oot值，沒關(guān)系，1照樣能一路找過來。
時(shí)間復(fù)雜度是O（nlgn），空間復(fù)雜度是O（n）。
例1.Graph Valid Tree。給出n個節(jié)點(diǎn)，序號從0~n-1，以及一個edge的list，表示一個無向圖，且edge不會重復(fù)，即假如已經(jīng)有[0,1]就不會再有[1，0]。返回這個圖是不是一棵樹。
【解】其實(shí)這道題是在問兩個問題：有沒有環(huán)？是不是一整個連通域？
環(huán)很好解決，假設(shè)V個節(jié)點(diǎn)，E條邊，沒有環(huán)的話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
時(shí)間和空間復(fù)雜度，和之前是一樣的。
2.Number of islands。海島個數(shù)。有一個mxn的全0矩陣，表示一片海，現(xiàn)在給出一個二維坐標(biāo)list，代表按照順序把對應(yīng)的坐標(biāo)置1，返回每一步操作之后海島的數(shù)目。所謂海島，就是通過上下左右相連的都是1的整個部分。比如給出n=m=3，和操作[[0,0],[0,1],[2,2],[2,1]]，返回[1,1,2,2]。（斜對角不算相連，不會對已經(jīng)是1的坐標(biāo)進(jìn)行操作，不會給出無效坐標(biāo)）。
【解】本質(zhì)上還是求連通域的個數(shù)。
首先進(jìn)行圖的轉(zhuǎn)換，因?yàn)橐笮蛱栐?~num-1，mxn矩陣總共有m*n個節(jié)點(diǎn)，因此每個節(jié)點(diǎn)的序號可以用行列數(shù)來決定，即row*n+col，序號從0到m*n-1。
然后每一步，看看周圍有沒有存在的連通域，這里需要考慮多個域在一個節(jié)點(diǎn)匯聚的情況，一個個都要merge，所以要依次遍歷上下左右。merge只需要把兩個點(diǎn)merge一下，路徑壓縮會自動把它們的root導(dǎo)到一起。因?yàn)樾蛱柖际遣恢貜?fù)的，所以假如碰到下一個連通域，照樣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
