1192. Critical Connections in a Network

https://leetcode.com/problems/critical-connections-in-a-network/

Python

Tarjan's algorithm

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        lowest_rank = [i for i in range(n)]

        graph = [[] for _ in range(n)]
        for connection in connections:
            graph[connection[0]].append(connection[1])
            graph[connection[1]].append(connection[0])

        visited = [False for _ in range(n)]

        def dfs(result, rank, pre_ver, cur_ver):
            nonlocal visited
            nonlocal lowest_rank

            visited[cur_ver] = True
            lowest_rank[cur_ver] = rank

            for next_ver in graph[cur_ver]:
                if next_ver == pre_ver:
                    continue

                if not visited[next_ver]:
                    dfs(result, rank + 1, cur_ver, next_ver)

                lowest_rank[cur_ver] = min(
                    lowest_rank[cur_ver],
                    lowest_rank[next_ver]
                )
                if lowest_rank[next_ver] >= rank + 1:
                    result.append([cur_ver, next_ver])

        result = []
        dfs(result, 0, -1, 0)
        return result