[LeetCode] 1192 | Critical Connections in a Network | Python

---

문제 링크: https://leetcode.com/problems/critical-connections-in-a-network/

---

문제

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [$a_i, b_i$] represents a connection between servers $a_i$ and $b_i$. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

---

조건

• 2 <= n <= $10^5$
• n - 1 <= connections.length <= $10^5$
• 0 <= $a_i, b_i$ <= n - 1
• $a_i$ != $b_i$
• There are no repeated connections.

---

내 풀이

모든 서버가 어떻게든 연결되어 있기 때문에 0번 서버에서 시작해서 dfs로 모든 서버를 둘러본다.

dfs는 0번 서버부터의 최소거리를 리턴한다.

visited에 self.num을 이용해 0번 서버에서부터의 거리를 저장한다.

dist_e > visited[s]를 만족시킨다면 s와 e 사이의 사이클이 존재하지 않는다는 의미므로, ans에 [s, e]를 추가한다.

사이클이 존재하지 않으면, 그 둘의 연결선을 끊었을 때 그 둘은 다시 연결될 수 없기 때문이다.

---

코드

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        G = defaultdict(list)
        visited = defaultdict(int)
        parent = [-1 for _ in range(n)]
        self.num = 0
        ans = []
        
        for s, e in connections:
            G[s].append(e)
            G[e].append(s)
        
        def dfs(s):
            if s in visited:
                return visited[s]
            
            visited[s] = self.num
            self.num += 1
            
            dist = float('inf')
            for e in G[s]:
                if e in visited:
                    if e != parent[s]:
                        dist = min(dist, visited[e])
                
                else:
                    parent[e] = s
                    dist_e = dfs(e)
                    
                    if dist_e > visited[s]:
                        ans.append([s, e])
                    
                    dist = min(dist, dist_e)
                    
            return dist
        
        dfs(0)
        return ans