Directed MST

Directed MST, Arborescence, Chu-Liu Edmonds, 최소 비용 신장 가지치기

정의

Directed MST (Arborescence) 는 유향 그래프와 루트 r 이 주어졌을 때, r 에서 모든 정점으로 도달 가능 한 간선들의 최소 가중치 부분집합을 구하는 문제. 무향 MST (Kruskal/Prim) 의 유향 버전.

각 정점이 루트가 아닌 한 정확히 한 개의 들어오는 간선을 선택. 사이클이 생기면 사이클 contraction 으로 해결. Chu-Liu / Edmonds 알고리즘이 고전 (1965/1967).

문제 상황과 동기

유향 그래프에서 루트 r 로부터 모든 정점에 도달하는 최소 비용 가지치기 (arborescence) 를 찾고 싶다. 무향 그래프는 Kruskal / Prim 으로 O(E log V) 이지만, 유향 그래프는 간선 방향 제약 + 사이클 처리 가 필요.

naive 하게 각 정점마다 최소 비용 들어오는 간선을 선택 하면 사이클이 생길 수 있다. 예: a ← b ← c ← a (사이클). 이 경우 사이클을 한 덩어리로 묶어 contract 한 뒤, 축소된 그래프에서 재귀적으로 풀고, expand 시 사이클 내 한 간선을 제거한다.

핵심 통찰: 사이클이 없으면 각 정점의 최소 간선이 답. 사이클이 있으면 사이클 전체를 슈퍼노드로 축소, 비용 보정 후 재귀. 펼칠 때 사이클 중 하나만 끊는다. O(VE) 또는 meldable heap 으로 O((V+E) log V).

PS 에서는 “의존성 트리 최소 비용”, “트리 구조 최적화” 같은 모델링 문제에 등장. ICPC / IOI 급에서 드물지만 표준 라이브러리 없어 직접 구현 필요.

시각화

핵심 아이디어 (Chu-Liu/Edmonds)

1. 루트가 아닌 각 정점에 대해 들어오는 간선 중 최소 비용 을 선택
2. 선택된 간선들로 그래프 구성 → 사이클이 없으면 종료, 답
3. 사이클이 있으면 사이클을 한 정점으로 contract, 사이클 비용 보정 후 재귀
4. 펼치기 (uncontract) 단계에서 어떤 간선을 끊을지 결정

chuLiuEdmonds(G, root):
    in_edge[v] = min cost incoming edge for each v ≠ root
    if 형성된 그래프에 사이클 없음: return in_edge
    cycle 들을 contract -> G'
    sub = chuLiuEdmonds(G', root')
    expand cycles, fix one edge in each cycle
    return sub + cycle edges - replaced

O(VE) 가 기본. Tarjan 의 meldable heap 기반 구현은 O((V+E) log V).

작은 예시

그래프:
  r --5--> a --3--> c
   \--2--> b --1--/
           b --4--> a

step 1: 각 정점의 최소 간선 선택
  a: (b, a, 4)
  b: (r, b, 2)
  c: (b, c, 1)

step 2: 그래프 구성
  r -> b -> c
       b -> a
  
  사이클 없음 → 답: {(r,b,2), (b,a,4), (b,c,1)} = 7

---

반례 (사이클 발생):
  r --5--> a --1--> b
           a <--2-- b

step 1: 각 정점 최소 간선
  a: (r, a, 5)
  b: (a, b, 1)

step 2: 그래프 구성
  r -> a -> b
       a <- b  ← 사이클!

step 3: contract {a, b} -> 슈퍼노드 X
  비용 보정: 외부에서 X 로 들어오는 간선은
             원래 비용 - (해당 정점이 사이클 내에서 선택한 간선 비용)
  예: (r, a, 5) -> (r, X, 5 - 0) = 5  (a 는 사이클 시작점)

step 4: 재귀 풀고 expand
  사이클 내 한 간선 제거 → (a, b, 1) 유지, (b, a, 2) 제거

복잡도

알고리즘	시간
기본 Chu-Liu/Edmonds	O(VE)
Tarjan/Gabow O((V+E) log V)	O((V+E) log V)
공간	O(V + E)

응용

1. 트리 / 가지치기 모델링

“한 모듈을 다른 모듈로부터 만들 수 있고, 비용 최소” 같은 의존성 그래프.

2. 외계 모드 LCT 연습

Dynamic Tree 의 결과를 검증할 때 brute reference.

3. ICPC 응용

대형 contest 에서 정점 만 단위 규모. 표준 라이브러리 (atcoder library) 가 없으므로 직접 구현.

구현

O(VE) 기본 Chu-Liu/Edmonds

// O(VE), 사이클 detect + contract + 재귀
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

struct Edge { int u, v; long long cost; };

long long directed_mst(int n, int root, vector<Edge> edges) {
    // in[v] = v 로 들어오는 최소 간선 인덱스
    vector<int> in(n, -1);
    for (int i = 0; i < (int)edges.size(); i++) {
        int v = edges[i].v;
        if (v == root) continue;
        if (in[v] == -1 || edges[i].cost < edges[in[v]].cost) {
            in[v] = i;
        }
    }
    
    // 사이클 detect (DFS)
    vector<int> vis(n, -1), cycle_id(n, -1);
    int num_cycles = 0;
    for (int i = 0; i < n; i++) {
        if (i == root || vis[i] >= 0) continue;
        int v = i;
        while (vis[v] < 0 && v != root) {
            vis[v] = i;
            if (in[v] == -1) break;
            v = edges[in[v]].u;
        }
        if (vis[v] == i) {
            // cycle found
            int w = v;
            do {
                cycle_id[w] = num_cycles;
                w = edges[in[w]].u;
            } while (w != v);
            num_cycles++;
        }
    }
    
    if (num_cycles == 0) {
        // no cycle → sum cost
        long long total = 0;
        for (int v = 0; v < n; v++) {
            if (v != root) total += edges[in[v]].cost;
        }
        return total;
    }
    
    // contract cycles
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    int new_n = 0;
    for (int v = 0; v < n; v++) {
        if (cycle_id[v] >= 0) id[v] = n + cycle_id[v];
        else id[v] = new_n++;
    }
    new_n += num_cycles;
    
    vector<Edge> new_edges;
    for (auto& e : edges) {
        int nu = id[e.u], nv = id[e.v];
        if (nu == nv) continue;  // 사이클 내부 간선
        long long new_cost = e.cost;
        if (cycle_id[e.v] >= 0) {
            // 사이클로 들어오는 간선: 비용 보정
            new_cost -= edges[in[e.v]].cost;
        }
        new_edges.push_back({nu, nv, new_cost});
    }
    
    long long cycle_cost = 0;
    for (int v = 0; v < n; v++) {
        if (cycle_id[v] >= 0 && in[v] >= 0) {
            cycle_cost += edges[in[v]].cost;
        }
    }
    
    return cycle_cost + directed_mst(new_n, id[root], new_edges);
}

실전에서는 meldable heap (pairing heap) 기반 O((V+E) log V) 구현을 권장 (koosaga, kactl).

함정

1. 루트로 도달 불가능한 정점

루트에서 모든 정점에 도달 가능해야 답 존재. 사전에 BFS 로 확인.

2. 사이클 contraction 의 비용 보정

새 contract 노드로 들어오는 간선 (u, w) 의 비용은 c(u,w) - c(in_edge[w]) 로 보정해야 옳다. 빠뜨리면 답이 틀림.

3. 구현 길이

기본 O(VE) 도 200 ~ 300 줄. 검증된 레퍼런스 (koosaga, kactl) 추천.

BOJ 연습 문제

번호	제목	링크
BOJ 16127	미생물 키우기	kokoa-lab
BOJ 19264	Hung Fu	kokoa-lab
BOJ 9582	Dictionary	kokoa-lab

다른 출처 연습 문제

출처	제목	링크
Library Checker	Directed MST	https://judge.yosupo.jp/problem/directedmst

참고

• Push-Relabel / Cost Scaling
• Dominator Tree
• Offline Dynamic MST