Today's Challenge

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

Critical Connections in a Network - LeetCode

오늘 문제는 조금 어려운듯..

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        g = defaultdict(list)
        
        for u, v in connections:
            g[u].append(v)
            g[v].append(u)
        
        l = len(g)
        
        time = [0 for _ in range(l)]
        low = [0 for _ in range(l)]
        ans = []
        
        def dfs(g, cur, pre, cnt):
            cnt += 1
            time[cur] = cnt
            low[cur] = cnt
            for nextv in g[cur]:
                if nextv == pre:
                    continue
                if time[nextv] == 0:
                    dfs(g, nextv, cur, cnt)
                    low[cur] = min(low[cur], low[nextv])
                else:
                    low[cur] = min(low[cur], time[nextv])
                if low[nextv] > time[cur]:
                    ans.append((cur, nextv))
        
        dfs(g, 0, -1, 0)
        return ans