# Matroid Union

Matroid Union은 여러 개의 matroid 독립 집합을 합쳐 얼마나 많은 원소를 덮을 수 있는지, 또는 한 ground set을 몇 개의 독립 집합으로 나눌 수 있는지를 다루는 reference 모델입니다. Matroid Intersection과 Parity가 "동시에 만족"과 "pair 단위 선택"을 본다면, Union은 "여러 독립 집합의 합"을 봅니다.

이 페이지는 Matroid Algorithms 허브 아래에서 Proof and Invariants 이후에 보는 그래프/조합 최적화 심화입니다.

1. 같은 ground set 위에 독립 집합을 여러 layer로 둔다.
2. 각 원소를 어떤 layer에 배치할 수 있는지 확인한다.
3. union rank와 covering 조건을 matroid 성질로 해석한다.

## 문제 신호

| 문제 표현 | Matroid Union 관점 |
| --- | --- |
| 원소를 여러 그룹에 나눠 각 그룹이 독립이어야 한다 | independent set union |
| 그래프 간선을 `k`개의 forest로 분해한다 | graphic matroid union |
| 색깔별 capacity가 있는 선택을 여러 번 할 수 있다 | partition matroid union |
| 전체 집합을 몇 개의 독립 집합으로 덮는지 묻는다 | matroid covering |
| rank formula나 exchange argument가 등장한다 | matroid union theorem 후보 |

대회에서는 일반 matroid oracle보다 graphic, partition, linear matroid처럼 구현 가능한 특수 형태로 나타나는 경우가 많습니다.

## 핵심 모델

matroid `M1, M2, ..., Mk`가 같은 원소 집합 `E` 위에 있다고 하겠습니다. 선택한 집합 `S`가 union matroid에서 독립이라는 뜻은 아래처럼 분해할 수 있다는 뜻입니다.

```text
S = S1 union S2 union ... union Sk
Si is independent in Mi
```

모든 `Mi`가 같은 matroid라면 "원소를 k개의 독립 집합으로 칠할 수 있는가"가 됩니다.

## Graphic Matroid 예시

그래프에서 forest는 graphic matroid의 독립 집합입니다. 간선 집합을 `k`개의 forest로 나눌 수 있다면 그 그래프의 arboricity가 `k` 이하라는 뜻입니다.

```text
간선 색 1: forest
간선 색 2: forest
...
간선 색 k: forest
```

cycle이 생긴 간선을 같은 색에 넣을 수 없으므로, 각 색마다 DSU를 하나씩 두는 greedy 검증을 떠올릴 수 있습니다. 하지만 임의 순서 greedy는 일반적으로 틀릴 수 있고, 막힌 간선을 넣기 위해 다른 색의 간선을 교환해야 할 수 있습니다.

중요한 판단 기준은 "지금 넣을 색이 없다"와 "어떤 분해에서도 넣을 수 없다"를 구분하는 것입니다. 한 색에서 cycle을 만드는 기존 간선 하나를 다른 색으로 밀어내면, 그 색에서도 또 다른 간선을 이동시키는 연쇄가 생길 수 있습니다. 따라서 forest decomposition류 문제에서는 실패 조건을 greedy 삽입 실패가 아니라 교환 경로 부재로 세워야 합니다.

## Partition Matroid의 쉬운 경우

원소마다 class가 있고, 한 독립 집합은 class별로 capacity만큼만 고를 수 있다고 합시다. 같은 matroid를 `k`번 union하면 class별 capacity가 `k`배가 됩니다.

class ID는 capacity 배열 범위, copies와 capacity는 비음수이며 item 개수는 int 범위입니다. 용량 곱은 long long으로 계산한 뒤 실제 item 개수로 제한합니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <algorithm>
#include <vector>
using namespace std;

int partitionMatroidUnionRank(
    const vector<int>& itemClass,
    const vector<int>& capacityPerClass,
    int copies
) {
    vector<int> count(capacityPerClass.size(), 0);
    for (int cls : itemClass) {
        ++count[cls];
    }

    int rank = 0;
    for (int cls = 0; cls < (int)capacityPerClass.size(); ++cls) {
        rank += (int)min((long long)count[cls], 1LL * copies * capacityPerClass[cls]);
    }
    return rank;
}
```

이 코드는 partition matroid처럼 독립성 조건이 완전히 분리될 때만 맞습니다. Graphic matroid나 linear matroid에서는 교환 구조가 필요합니다.

## Union Rank 직관

Matroid Union Theorem은 union rank를 아래 형태의 min formula로 설명합니다.

```text
r_union(X) = min over A subset X of |X - A| + r1(A) + r2(A) + ... + rk(A)
```

직관적으로 `A` 안의 원소들은 각 matroid rank로 감당해야 하고, `X - A`는 그냥 버리거나 직접 세는 부분입니다. 이 식을 그대로 구현하는 경우는 드물지만, 왜 단순 greedy가 부족한지 보여 줍니다.

## Exchange가 필요한 이유

새 원소 `e`가 어떤 layer에도 바로 들어가지 않는다고 해서 실패는 아닙니다. 한 layer에서 cycle이나 rank conflict가 생기면, 그 layer의 기존 원소 하나를 다른 layer로 보내고 `e`를 넣는 연쇄 교환이 가능할 수 있습니다.

```text
e enters layer 1
old edge a moves from layer 1 to layer 2
old edge b moves from layer 2 to layer 3
...
```

이 관점은 Matroid Intersection의 exchange graph와 닮았지만, "layer 사이 이동"이 중심이라는 점이 다릅니다.

## 문제별 구현 선택

| 구조 | 가능한 접근 |
| --- | --- |
| partition matroid | class별 count/capacity |
| graphic matroid 작은 입력 | 색별 DSU + backtracking/augmenting |
| linear matroid 작은 rank | basis rollback과 augmenting search |
| arboricity 판정 | Nash-Williams 조건, flow/modeling 후보 |
| 일반 oracle matroid | 대회 구현 범위를 넘기 쉬움 |

문제가 일반 matroid union을 요구하는 것처럼 보여도, 실제로는 그래프 density 조건이나 partition capacity로 단순화되는 경우가 많습니다.