1 분 소요

문제

Critical Connections in a Network - LeetCode

문제 접근

  • cycle에 포함된 에지들의 경우, 지워도 상관 없다.
  • cycle을 어떻게 판별하는가? => dfs 탐색하다가 같은 노드를 재방문하면 cycle
  • 문제는 cycle에 포함된 모든 에지들에 대해서 삭제를 해야하는데 이걸 어떻게 구현하나? → 여기서 막힘

핵심 개념

  • RANK

image

문제 풀이

from collections import defaultdict
from typing import List
# 모든 커넥션을 하나씩 지워본다 -> 그리고 dfs 탐색해서 방문 못하는 노드가 있으면 해당 connection을 정답에 추가한다.
# cycle에 포함된 에지들의 경우, 지워도 상관 없다.
# cycle을 어떻게 판별하는가? => dfs 탐색하다가 같은 노드를 재방문하면 cycle => 이걸 어디에 어떻게 저장하지?
# Depth First Search for Cycle Detection
class Critical_Connections_in_a_Network:

    rank = {}
    graph = defaultdict(list)
    edges = {}      # directly/in-directly connected nodes {(u,v), (x,y), ...}   -> 모든 에지들 (여기서 cycle에 포함된 에지들은 뺄 예정)

    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        self.formGraph(n, connections)

        self.dfs(0,0)

        result = []
        for u, v in self.edges:
            result.append([u, v])

        return result

    def dfs(self, node: int, discovery_rank: int) -> int:
        # 이미 방문한 노드면(None이 아니면), rank 반환
        if self.rank[node]:
            return self.rank[node]

        # Update the rank of this node.
        self.rank[node] = discovery_rank

        # This is the max we have seen till now. So we start with this instead of INT_MAX or something
        min_rank = discovery_rank + 1
        for neighbor in self.graph[node]:

            # Skip the parent
            if self.rank[neighbor] and self.rank[neighbor] == discovery_rank - 1:
                continue

            # Recurse on the neighbor
            recursive_rank = self.dfs(neighbor, discovery_rank+1)

            # Step 1. Check if this edge needs to be discarded
            if recursive_rank <= discovery_rank:
                del self.edges[(min(node, neighbor), max(node, neighbor))]

            # Step 2. Update the minRank if needed
            min_rank = min(min_rank, recursive_rank)

        return min_rank

    def formGraph(self, n: int, connections: List[List[int]]):
        # Reinitialize for each test case
        self.rank = {}
        self.graph = defaultdict(list)
        self.edges = {}

        # Default rank for unvisited nodes is "null"
        for i in range(n):
            self.rank[i] = None

        for u, v in connections:
            self.graph[u].append(v)
            self.graph[v].append(u)

            self.edges[(min(u,v), max(u,v))] = 1    # edges[(u,v)] = 1 : u와 v는 직접적으로 연결됨

참고