[BOJ 11266] 단절점

문제

---

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

풀이

---

사실 SCC (Strongly Connected Component)를 완벽히 이해하지 못한 것 같은 찜찜함이 있었는데, BCC (Biconnected Component)를 배우면서 SCC부터 제대로 정리해야겠단 생각이 들었다.

우선 단절점을 찾는 문제는 dfs tree에서 dfsn만 잘 관찰해도 풀 수 있다.

임의의 노드를 루트 노드로 잡고 dfs tree를 만들어보자.

그래프에서 어떤 노드가 단절점이 아니라는 것은, 그 노드를 제거했을 때 connected component 수가 그대로인 것과 동치이다.

그러므로 dfs tree의 루트 노드가 아닌 어떤 노드가 단절점이 아니라는 것은, 그 노드의 부모 노드와 자식 노드들이 연결되어 있어야 한다.

즉, 자식 노드들의 low 값이 그 노드의 dfsn 값보다 작아야 한다.

단 하나의 자식 노드라도 low 값이 그 노드의 dfsn 값보다 크거나 같으면, 그 노드는 단절점이 된다.

루트 노드가 단절점이 아니라면 dfs tree 상에서 자식 노드가 하나 이하여야 한다.

코드

---

import sys
sys.setrecursionlimit(10 ** 4)

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)


def dfs(cur, root):
    global idx
    dfsn[cur] = idx
    low = idx
    idx += 1
    num = 0
    flag = True

    for nxt in graph[cur]:
        if dfsn[nxt]:
            low = min(low, dfsn[nxt])
        
        else:
            num += 1
            child = dfs(nxt, False)
            low = min(low, child)
            if not root and flag and (dfsn[cur] <= child):
                articulation.append(cur)
                flag = False

    if root and (num > 1):
        articulation.append(cur)
    
    return low


for i in range(1, n + 1):
    if not dfsn[i]:
        idx = 1
        dfs(i, True)

print(len(articulation))
print(*sorted(articulation))