Python에서 그래프 연결을 끊는 간선을 찾는 프로그램

<시간/>

인접 목록으로 표시된 무방향 그래프가 제공되었다고 가정합니다. 여기서 graph[i]는 노드 i의 인접 노드를 나타냅니다. 다음 조건을 만족하는 간선의 수를 찾아야 합니다.

에지가 제거되면 그래프의 연결이 끊어집니다.

So, if the input is like graph = [
   [0, 2],
   [0, 4],
   [1, 2, 3],
   [0, 3, 4],
   [4],
   [3],
   [2]
],

그러면 출력은 1이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

함수 dfs()를 정의합니다. curr, pre, d
가 필요합니다.
- ans :=무한대
- dep[curr] :=d
- 그래프[curr]의 각 adj에 대해 수행
  - pre가 adj와 같으면
    - 다른 단계를 수행하지 않고 다음 반복을 계속합니다.
  - dep[adj]가 -1과 같지 않으면
    - ans :=ans의 최소값, dep[adj]
  - 그렇지 않으면
    - ans :=ans의 최소값, dfs(adj, curr, d + 1)
- d> 0이고 d <=ans이면
  - 다시 :=다시 + 1
- 반환
이제 주 함수에서 dfs() 함수를 호출합니다.
dep :=-1로 초기화된 그래프의 크기 목록.
다시 :=0
dfs(0, -1, 0)
다시 돌아가기

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

class Solution:
   def solve(self, graph):
      dep = [−1] * len(graph)
      INF = int(1e9)
      self.re = 0
      def dfs(curr, pre, d):
         ans = INF
         dep[curr] = d
         for adj in graph[curr]:
            if pre == adj:
               continue
            if dep[adj] != −1:
               ans = min(ans, dep[adj])
            else:
               ans = min(ans, dfs(adj, curr, d + 1))
         if d > 0 and d <= ans:
            self.re += 1
         return ans
      dfs(0, −1, 0)
      return self.re
ob = Solution()
print(ob.solve(graph = [
   [0, 2],
   [0, 4],
   [1, 2, 3],
   [0, 3, 4],
   [4],
   [3],
   [2]
]))

입력

graph = [
   [0, 2],
   [0, 4],
   [1, 2, 3],
   [0, 3, 4],
   [4],
   [3],
   [2]
]