[python] 백준 11400 단절선

https://www.acmicpc.net/problem/11400

 

문제 해결

• 사이클이 만들어지는 선들은 하나가 끊긴다고 안이어지지 않는다.
• 사이클이 안만들어지는 연걸선이 단절선이 된다.
• 따라서 그에 관한 DFS 알고리즘을 사용하면 된다.

CODE

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


def dfs(start ,parent):
    global cnt
    cnt += 1
    visited[start] = True
    visit_order[start] = cnt
    lsv = visit_order[start]

    for childNode in graph[start]:
        if childNode == parent:continue # 이전의 점이 다음점으로 이동하는 것 방지(사이클이 아닌 단순 왔다갔다 방지)

        if visited[childNode] == True:
            lsv = min(lsv, visit_order[childNode])
            continue

        subtree = dfs(childNode, start)
        lsv = min(subtree, lsv)

        if subtree > visit_order[start]: # 사이클이 안돌아지는 부분
            bridge.add(tuple(sorted([start, childNode])))
    return lsv

            

if __name__ == "__main__":
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    visited = [0 for _ in range(v+1)]
    visit_order = [0 for _ in range(v+1)] # 최소 사이클 그룹

    for i in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    cnt = 0
    bridge = set()
    
    dfs(1, None)

    bridge = sorted(bridge,key = lambda x : (x[0], x[1]))
    print(len(bridge))
    for x, y in bridge:
        print(x,y)