Tarjan's Algo

Tarjan's Algorithm to find Articulate point

Link Video

Traverse node, 紀錄每個node是第幾步(step), dfs 之後update其可以接觸的最小node以判斷是否cycle

Articulate point 發生在

1. Node u 沒有parent(起始點)且有大於兩個subtree時

2. Node u有parent, 且有一個child v及其subtree not chaining back to on of ancestors of u

from collections import defaultdict
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        # build graph
        self.graph = defaultdict(list)
        for conn in connections:
            self.graph[conn[0]].append(conn[1])
            self.graph[conn[1]].append(conn[0])
            
        # init [], low[]
        self.count = [-1] * n
        self.low = [-1] * n
        self.parent = [-1] * n
        self.critical = [False] * n
        
        for i in range(n):
            if self.count[i] == -1:
                self.dfs(i, 0)
        
        ans = [i for i, x in enumerate(self.critical) if x is True]
        print(ans)
        return ans
    
    
    # Tarjan algo
    def dfs(self, u, step):
        self.count[u] = self.low[u] = step
        step+=1
        tree = 0
        for v in self.graph[u]:
            self.parent[v] = u
            if self.count[v] == -1:
                self.dfs(v, step)
                tree+= 1
                # 此時low已經被後面的node更新過，若找到circle則更新smallest visit count
                self.low[u] = min(self.low[u], self.low[v])
                
                # (1) u is root of DFS tree and has two or more distict subtree
                if self.parent[u] == -1 and tree >= 2:
                    self.critical[u] = True
                #(2) If u is not root and low value of one of its child is more 
                # than discovery value of u. 
                if self.parent[u] != -1 and self.count[u] < self.low[v]:
                    self.critical[u] = True
            
            
            elif self.parent[u] != v:
                # 找到circle的連結點，更新low[u]
                self.low[u] = min(self.low[u], self.count[v])

1192 Critical Connections in a Network (find edge)

from collections import defaultdict
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:   
     # build graph
    self.graph = defaultdict(list)
    for conn in connections:
        self.graph[conn[0]].append(conn[1])
        self.graph[conn[1]].append(conn[0])

    # init [], low[]
    self.count = [-1] * n
    self.low = [-1] * n
    self.parent = [-1] * n
    self.ans = []

    for i in range(n):
        if self.count[i] == -1:
            self.dfs(i, 0)

    return self.ans


# Tarjan algo
def dfs(self, u, step):
    self.count[u] = self.low[u] = step
    step+=1
    for v in self.graph[u]:
        self.parent[v] = u
        if self.count[v] == -1:
            self.dfs(v, step)
            # 此時low已經被後面的node更新過，若找到circle則更新smallest visit count
            self.low[u] = min(self.low[u], self.low[v])

            # 若u不是起始點
            # 若v之後的node有circle，則low[v]應該小於low[u]，沒有circle則是criticle point
            if self.parent[u] != -1 and self.count[u] < self.low[v]:
                self.ans.append([u, v])

        elif self.parent[u] != v:
            # 找到circle的連結點，更新low[u]
            self.low[u] = min(self.low[u], self.count[v])