단절점·다리 찾기

정점 하나를 지웠을 때 연결 요소가 늘어나면 그 정점이 단절점이고, 간선 하나를 지웠을 때 늘어나면 그 간선이 다리입니다. 네트워크로 보면 라우터 하나가 죽어 망이 두 동강 나는 자리, 회선 하나가 끊겨 지사가 고립되는 자리가 그것입니다. 정의가 「지워 보면 안다」라서 전수로도 구할 수 있지만, 타잔의 깊이 우선 탐색은 한 번의 훑기로 전부 찾아냅니다.

그 정점의 서브트리에서 트리 간선을 거꾸로 타지 않고 되돌아갈 수 있는 가장 작은 발견 순번(disc)입니다. 되돌아가는 길은 역방향 간선뿐입니다. 트리 간선 u—v에서 low[v] > disc[u]이면 v 쪽에서 u를 건너뛰고 위로 올라갈 길이 아예 없다는 뜻이라 그 간선이 다리입니다.

있습니다. 판정식의 부등호가 다르기 때문입니다. 다리는 low[v] > disc[u], 단절점은 low[v] >= disc[u]입니다. 부등호가 하나 느슨한 것은 v가 u 자신까지는 돌아올 수 있어도 u를 지우면 그 길마저 사라지기 때문입니다. 삼각형 두 개가 한 정점에서 만나는 모양이 그렇습니다 — 그 정점은 단절점이지만 다리는 하나도 없습니다.

시작 정점에는 위로 올라갈 부모가 없어 같은 식을 쓸 수 없기 때문입니다. 뿌리는 DFS 트리에서 자식이 둘 이상일 때만 단절점입니다. 자식이 하나면 그 정점을 지워도 나머지가 한 덩어리로 남습니다. 이 예외를 빠뜨리는 것이 이 알고리즘에서 가장 흔한 구현 실수입니다.

어느 쪽도 다리가 아니게 됩니다. 한 줄을 끊어도 다른 줄이 남기 때문입니다. 구현에서는 되돌아온 길이 부모인지 판정할 때 정점 이름으로 비교하면 두 번째 줄까지 부모로 오인해 무시하게 되어 다리가 아닌 간선을 다리로 잘못 잡습니다. 그래서 간선마다 번호를 붙여 들어온 그 번호만 건너뛰어야 합니다. 자기 자신으로 가는 간선은 연결성에 영향이 없어 처음부터 버립니다.

그쪽은 방향 그래프에서 서로 오갈 수 있는 묶음을 찾고, 이쪽은 무향 그래프에서 끊어지는 자리를 찾습니다. low-link라는 이름과 깊이 우선 탐색 뼈대가 닮아 헷갈리기 쉽지만 대상도 판정식도 다릅니다. 순환 의존을 볼 때는 SCC, 이중화가 필요한 자리를 볼 때는 이쪽입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.