DFS 트리 찾기

처음에는 각 정점을 하나의 컴포넌트로 본다. 이미 선택한 트리 간선으로 합쳐진 정점들은 하나의 컴포넌트로 수축한다.

현재 컴포넌트 $B$의 진입 간선은 꼬리가 $B$ 밖에 있고 머리가 $B$ 안에 있는 원래 방향 간선이다. 진입하는 서로 다른 컴포넌트의 수가 아니라, 방향 간선의 개수 자체를 센다는 점에 주의해야 한다.

진입 간선이 정확히 하나인 컴포넌트 $B$를 찾는다. 그 유일한 간선을 $u \to v$라 하고, $u$가 속한 컴포넌트를 $A$라 하자. $u \to v$를 트리 간선으로 선택하여 $P_v=u$로 정하고, $A$와 $B$를 하나의 컴포넌트로 합친다. 새 컴포넌트의 루트 정점은 기존 $A$의 루트 정점이다.

이 과정을 더 이상 수행할 수 없을 때까지 반복한다.

정당성

컴포넌트 $B$의 진입 간선이 $u \to v$ 하나뿐일 때 $B$를 $A$ 아래에 붙였다고 하자. 두 컴포넌트 사이에서 $A$ 쪽에서 $B$ 쪽으로 향하는 간선은 이 간선 하나뿐이다. 따라서 두 컴포넌트가 합쳐질 때 새로 내부 간선이 되는 다른 모든 간선은 에서 로 향한다. 이 간선들은 새 트리에서 자손 쪽 컴포넌트에서 조상 쪽 컴포넌트로 향한다. 기존 컴포넌트 내부의 조건도 귀납적으로 유지된다.

반대로 유효한 트리가 존재하고 컴포넌트가 둘 이상이라고 하자. 선택된 트리 간선만 남겨 컴포넌트들을 하나의 정점으로 수축하면 컴포넌트들 사이에도 루트 있는 트리가 생긴다. 이 트리의 리프 컴포넌트에는 부모 컴포넌트에서 오는 트리 간선 하나만 진입할 수 있다. 리프 컴포넌트 밖에는 그 컴포넌트의 자손이 없으므로, 트리에 속하지 않은 역방향 간선이 추가로 진입할 수도 없다. 따라서 진입 간선이 정확히 하나인 컴포넌트가 반드시 존재한다.

진입 간선이 하나인 컴포넌트를 먼저 수축하는 선택들은 서로 교환할 수 있다. 한 수축은 관련되지 않은 다른 컴포넌트의 진입 간선 집합을 바꾸지 않으며, 두 관련 컴포넌트를 합친 것으로만 치환된다. 따라서 어떤 순서로 가능한 수축을 골라도, 유효한 트리가 존재한다면 최종적으로 하나의 컴포넌트에 도달한다.

최종적으로 컴포넌트가 하나라면 선택한 $N-1$개의 간선이 조건을 만족하는 트리이다. 컴포넌트가 둘 이상인데 진입 간선이 하나인 컴포넌트가 없다면 유효한 트리는 존재하지 않는다.

효율적인 구현

각 컴포넌트에 다음 정보를 저장한다.

• 컴포넌트에 속한 정점 목록
• 컴포넌트로 들어오는 외부 간선 번호의 해시 집합
• 아직 부모가 정해지지 않은 컴포넌트의 루트 정점

두 컴포넌트를 합칠 때 정점 수가 작은 쪽을 큰 쪽으로 옮긴다.

작은 컴포넌트의 모든 정점에서 나가는 간선을 확인하면, 작은 컴포넌트에서 큰 컴포넌트로 향하여 내부 간선이 되는 간선을 큰 컴포넌트의 진입 간선 집합에서 지울 수 있다. 작은 컴포넌트의 진입 간선 집합도 큰 쪽으로 옮기되, 꼬리가 큰 컴포넌트에 있는 간선은 내부 간선이므로 버린다.

작은 쪽의 정점 수는 이동할 때마다 두 배 이상이 된다. 따라서 각 정점과 각 간선은 $O(\log N)$번만 처리된다. 해시 집합을 사용하면 기대 시간 복잡도는 $O((N+M)\log N)$이고, 공간 복잡도는 $O(N+M)$이다.