685. 冗余连接 II
- 思路
- example
- 有向图，并查集
有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
-
入度，出度 (无向图不需要这个概念）
edge = [a, b], 起点：a, 终点：b
如果存在入度为2的顶点，最后要构成树，那么删除的边一定为该顶点的某一条入边
如果不存在入度为2的顶点，那我们可以直接删除加入会构成环的边 （同684. 冗余连接）
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
def union(node1, node2): # [node1, node2], node1 -> node2
ancestor[find(node2)] = find(node1)
def find(node): # find node's ancestor
if ancestor[node] != node:
ancestor[node] = find(ancestor[node])
return ancestor[node]
def check_tree(edges, removed):
for edge in edges:
if edge == removed: # removed是删掉的edge
continue
if find(edge[0]) == find(edge[1]): # 有共同的祖先节点
return False # 不是 有根树
else: # 没有共同祖先节点
union(edge[0], edge[1]) # 连结两个节点 使得具有共同祖先
return True # 是 有根树
# main code
n = len(edges)
inDegree = [0 for _ in range(n+1)]
deg2_index = -1
for i in range(n): # edges = [*, *]
inDegree[edges[i][1]] += 1
if inDegree[edges[i][1]] == 2:
deg2_index = i # save the edge with end point having in-degree 2
# 第一种情况：含有in-degree 2 的情况 (可能有环), 删除其中一个入边使得剩下的edges成为 有根树
ancestor = list(range(n+1))
if deg2_index != -1:
if check_tree(edges, edges[deg2_index]) == True: # 删掉该edge后成为有根树
return edges[deg2_index] # 返回该edge
else: # 否则应该删掉另一条入边
node1 = edges[deg2_index][0]
node2 = edges[deg2_index][1]
for edge in edges:
if edge[0] != node1 and edge[1] == node2:
return edge
# 第二种情况：不含有in-degree 2 的情况，此时必有环 (同 #684)
ancestor = list(range(n+1))
for edge in edges:
node1, node2 = edge[0], edge[1]
if find(node1) == find(node2):
return edge
else:
union(node1, node2)
547. 省份数量
- 思路
- example
- 无向图
- DFS
- 建立无向图(dict(list)) --- 也可以直接用isConnected矩阵， 然后dfs标记连通城市，使用visited避免重复访问
- 并查集
- 复杂度. 时间：
, 空间:
# 这里先考虑DFS
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
def dfs(index):
visited.add(index)
for j in range(n):
if isConnected[index][j] == 1 and j not in visited:
dfs(j)
n = len(isConnected) # number of cities
visited = set()
res = 0 # number of provinces
for i in range(n): # city i
if i not in visited:
dfs(i)
res += 1
return res
