685. 冗余連接 II

• 思路
  • example
  • 有向圖，并查集

有根樹指滿足以下條件的 有向 圖。該樹只有一個根節(jié)點，所有其他節(jié)點都是該根節(jié)點的后繼。該樹除了根節(jié)點之外的每一個節(jié)點都有且只有一個父節(jié)點，而根節(jié)點沒有父節(jié)點。

• 入度，出度 (無向圖不需要這個概念）

  
  
  
  

edge = [a, b], 起點：a, 終點：b
如果存在入度為2的頂點，最后要構成樹，那么刪除的邊一定為該頂點的某一條入邊
如果不存在入度為2的頂點，那我們可以直接刪除加入會構成環(huán)的邊 （同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]): # 有共同的祖先節(jié)點 
                    return False  # 不是 有根樹
                else: # 沒有共同祖先節(jié)點
                    union(edge[0], edge[1]) # 連結兩個節(jié)點 使得具有共同祖先
            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 的情況 (可能有環(huán)), 刪除其中一個入邊使得剩下的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 的情況，此時必有環(huán) (同 #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. 省份數(shù)量

• 思路
  • 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