[백준 11400번] 단절선 (Python3)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def DFS(now,last):
  global id
  visited[now] = ID[now] = id
  for next in graph[now]:
    if next==last:
      continue
    if not visited[next]:
      id += 1
      DFS(next,now)
      if ID[next]==visited[next]:
        result.append(sorted((now,next)))
    visited[now] = min(visited[now],visited[next])

N,M = map(int,input().split())
graph = [[] for i in range(N+1)]
for _ in range(M):
  a,b = map(int,input().split())
  graph[a].append(b); graph[b].append(a)
visited = [0]*(N+1); ID = [0]*(N+1)
result = []
for i in range(1,N+1):
  if not visited[i]:
    id = 1
    DFS(i,i)
print(len(result))
for r in sorted(result):
  print(*r)

단절선 알고리즘 기본문제

단절점 [백준 11266번] 단절점 (Python3) (tistory.com) 과 풀이가 비슷하지만 더 쉽고 예외도 적다.

여러가지 요소를 고려해주어야 했던 단절점 문제와 달리 단절선 문제는 자식노드가 이전방문노드로 갈 수 있는지의 여부만 확인하면 된다. 자식노드가 방문번호가 더 작은 노드로 갈 수 없으면 현재노드-자식노드 의 간선이 단절선이다.