간선 소매넣기

추가 간선을 포함한 무향 그래프를 $H$라 하자. $G$가 연결되어 있으므로 추가 간선의 두 끝점 사이에는 이미 경로가 존재한다. 따라서 추가 간선은 $H$에서 어떤 사이클 위에 있으며, 하나의 비자명한 이중 연결 요소에 속한다.

여기서 비자명한 이중 연결 요소는 간선을 하나만 갖는 다리 블록이 아닌 정점 이중 연결 요소를 뜻한다. 간선들은 이러한 블록들로 분할된다.

st-ordering을 사용한다. 이중 연결 그래프와 그 안의 간선 $(s,t)$가 주어지면, 다음 조건을 만족하는 정점 순서가 존재하며 선형 시간에 구할 수 있다.

• $s$가 첫 번째이고 $t$가 마지막이다.
• $s,t$가 아닌 모든 정점은 자신보다 앞선 이웃과 뒤의 이웃을 각각 하나 이상 갖는다.

첫 번째 실행에서는 $H$의 이중 연결 요소를 구한다.

추가 간선이 속한 블록에서는 추가 간선의 두 끝점을 $s,t$로 잡아 st-ordering을 구한다. 모든 간선을 순서가 작은 정점에서 큰 정점으로 향하게 한다. 그러면 이 블록에서 $s$만 내부 진입 차수가 $0$이고, $t$만 내부 진출 차수가 $0$이다. 또한 $s$에서 로 향하는 간선은 정확히 추가 간선이다.

추가 간선이 속하지 않은 각 비자명한 블록에서는 임의의 간선 $(s,t)$를 하나 고른다. st-ordering을 구한 뒤, 고른 간선을 제외한 모든 간선을 순서가 작은 쪽에서 큰 쪽으로 향하게 하고, 고른 간선만 $t$에서 $s$로 뒤집는다. 내부 정점은 st-ordering의 성질로 진입 간선과 진출 간선을 모두 가진다. $s$는 뒤집은 간선으로 진입 간선을 얻고, $t$는 그 간선으로 진출 간선을 얻는다. 따라서 이 블록의 모든 정점은 내부 진입 차수와 내부 진출 차수가 모두 양수이다.

다리는 어느 방향으로 두어도 된다. 두 번째 실행에서는 방향을 무시하고 이중 연결 요소를 다시 구할 수 있으므로 다리 블록은 조사하지 않는다.

두 번째 실행에서 각 비자명한 블록의 내부 간선만 사용하여 진입 차수와 진출 차수를 계산한다. 정확히 하나의 블록에서만 내부 진입 차수가 $0$인 정점 $s$와 내부 진출 차수가 $0$인 정점 $t$가 하나씩 발견된다. 그 블록의 $s\to t$ 간선이 추가 간선이다.

정점 및 간선 번호의 순열은 이중 연결 요소와 내부 차수 성질을 바꾸지 않으므로 항상 복원할 수 있다.

Tarjan 알고리즘으로 이중 연결 요소를 구하고, 각 블록에서 st-ordering을 구하면 두 실행 모두 $O(N+M)$ 시간과 $O(N+M)$ 메모리를 사용한다.