Count 计数
统计每个联通块的元素个数
LintCode 590. Connecting Graph II
- query(a), Returns the number of connected component nodes which include node a.
class ConnectingGraph2:
def __init__(self, n):
self.root = range(n+1)
self.size = [1] * (n+1)
def find(self, x):
root = self.root
if root[x] == x:
return x
root[x] = self.find(root[x])
return root[x]
def connect(self, a, b):
root = self.root
size = self.size
roota = self.find(a)
rootb = self.find(b)
if roota != rootb:
root[roota] = rootb
size[rootb] += size[roota]
def query(self, a):
return self.size[self.find(a)]
统计连通块的个数
the number of connected components.
LintCode 591. Connecting Graph III
- Query() - Returns the number of connected component in the graph
class ConnectingGraph3:
def __init__(self, n):
self.root = range(n+1)
self.cnt = n
def find(self, x):
root = self.root
if root[x] == x:
return x
root[x] = self.find(root[x])
return root[x]
def connect(self, a, b):
root = self.root
roota = self.find(a)
rootb = self.find(b)
if roota != rootb:
root[roota] = rootb
self.cnt -= 1
def query(self):
return self.cnt
323. Number of Connected Components in an Undirected Graph
- 解法1. DFS
将Graph原本的nodes和edges表达形式，改成hash做的邻接表，这个就可以查询从每个节点出发到的节点！
class Solution(object):
def countComponents(self, n, edges):
visited = [0] * n
graph = [set() for _ in xrange(n)] # Adjacent Table
for i, j in edges:
graph[i].add(j)
graph[j].add(i)
res = 0
for i in xrange(n):
if visited[i] == 1:
continue
self.dfs(i, visited, graph)
res += 1
return res
def dfs(self, n, visited, graph):
if visited[n] == 1:
return
visited[n] = 1
for i in graph[n]:
self.dfs(i, visited, graph)
- 解法2. Union Find
class Solution(object):
def countComponents(self, n, edges):
root = range(n)
self.cnt = n
def find(x):
if root[x] == x:
return x
root[x] = find(root[x])
return root[x]
def union(x, y):
rootx = find(x)
rooty = find(y)
if rootx != rooty:
root[rootx] = rooty
self.cnt -= 1
for i, j in edges:
union(i, j)
return self.cnt
305. Number of Islands II
实时放入island显示出联通块的个数，算是一个online的算法！
- 原始UF算法是一维的，2D坐标和1D坐标的转化
- 体现Union Find的Online特性，可以实时添加边！
# Time : O(m * n + k)
class UnionFind(object):
def __init__(self, n):
self.root = [-1] * n
self.cnt = 0
def find(self, x):
root = self.root
if root[x] == x:
return x
root[x] = self.find(root[x])
return root[x]
def add(self, x):
self.root[x] = x
self.cnt += 1
def union(self, x, y):
root = self.root
rootx = self.find(x)
rooty = self.find(y)
if rootx != rooty:
root[rootx] = rooty
self.cnt -= 1
class Solution(object):
def numIslands2(self, m, n, positions):
uf = UnionFind(m * n)
res = []
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i, j in positions:
p = i*n + j
uf.add(p)
for k in range(4):
ni, nj = i + d[k][0], j + d[k][1]
q = ni * n + nj
if ( 0 <= ni <= m-1 and
0 <= nj <= n-1 and
uf.root[q] != -1):
uf.union(p, q)
res.append(uf.cnt)
return res
547. Friend Circles
class Solution(object):
def findCircleNum(self, M):
n = len(M)
root = range(n)
self.cnt = n
def find(x):
if root[x] == x:
return x
root[x] = find(root[x])
return root[x]
def union(x, y):
rootx = find(x)
rooty = find(y)
if rootx != rooty:
root[rootx] = rooty
self.cnt -= 1
for i in xrange(n):
for j in xrange(i+1, n):
if M[i][j]:
union(i, j)
return self.cnt
Redundant Connection
261. Graph Valid Tree
class Solution(object):
def validTree(self, n, edges):
root = range(n)
self.cnt = n
def find(x):
if root[x] == x:
return x
root[x] = find(root[x])
return root[x]
def union(x, y):
rootx = find(x)
rooty = find(y)
if rootx != rooty:
root[rootx] = rooty
self.cnt -= 1
return True
return False
for i, j in edges:
if not union(i, j):
return False
return self.cnt == 1
684. Redundant Connection
class Solution(object):
def findRedundantConnection(self, edges):
root = range(1001)
def find(x):
if root[x] == x:
return x
root[x] = find(root[x])
return root[x]
for i, j in edges:
rooti = find(i)
rootj = find(j)
if rooti == rootj:
return [i, j]
root[rooti] = rootj
685. Redundant Connection II
- Case1: There is a loop in the graph, and no vertex has more than 1 parent.
- 有环，且没有入度大于1的node => Union Find
- Case2: A vertex has more than 1 parent, but there isn't a loop in the graph.
- 无环，且有入度大于2的node => last node (indegree > 1)
- Case3: A vertex has more than 1 parent, and is part of a loop.
- 有环，且有入度大于2的node
- 这种复杂的情况怎么筛选?
- Delete the second edge!
class Solution(object):
def findRedundantDirectedConnection(self, edges):
n = len(edges)
parent = [0] * (n+1)
ans = None
# Step1 : calculate indegree > 1 node
for i in xrange(n):
u, v = edges[i]
if parent[v] == 0:
parent[v] = u
else:
ans = [[parent[v], v], [u, v]]
# !!! Delete the second Edge
edges[i][1] = 0
# Step2 : Union Find detect cycle
root = range(n+1)
def find(x):
if root[x] == x:
return x
return find(root[x])
for u, v in edges:
rootu = find(u)
rootv = find(v)
if rootu == rootv: # Detect Cycle
if not ans:
return [u, v]
else:
return ans[0]
root[rootu] = rootv
return ans[1]