[BOJ 11400] 단절선

문제

---

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

풀이

---

단절점에 이어서 단절선을 구하는 문제이다.

마찬가지로 dfs tree에서 dfsn과 관련지어 생각해 보자.

어떤 노드의 dfsn보다 자식 노드의 low 값이 strict하게 크면 그 노드와 자식 노드를 잇는 엣지는 단절선이 된다.

코드

---

import sys
sys.setrecursionlimit(10 ** 5)

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

articulation = []
dfsn = [0] * (n + 1)
idx = 1


def dfs(cur, parent):
    global idx
    dfsn[cur] = idx
    low = idx
    idx += 1

    for nxt in graph[cur]:
        if nxt == parent:
            continue

        if dfsn[nxt]:
            low = min(low, dfsn[nxt])
        else:
            child = dfs(nxt, cur)
            low = min(low, child)
            if dfsn[cur] < child:
                articulation.append(tuple(sorted((cur, nxt))))
    
    return low


dfs(1, 0)

articulation.sort()
print(len(articulation))
for edge in articulation:
    print(*edge)

인접 리스트 graph를 이용해 dfs를 하는 과정에서, nxt가 부모 노드일 때는 low 값을 갱신하면 안 된다.

그렇지 않으면 child는 dfsn[cur] 이하가 돼서 간절선을 찾을 수 없게 되기 때문이다.

그래서 dfs의 파라미터로 parent를 넣어줘야 한다.

이 문제에선 연결 그래프란 가정이 있었으므로 dfs를 1번만 돌려주면 된다.

참고로 pypy3은 맞은 사람이 없는 걸로 보아 무조건 메모리 초과가 뜨는 것 같다.