이 제약이라고 다니지 않는다고 생각하면 최대 매칭으로 풀 수 있었는지..라는 문제. 상정해에서는 DSU를 사용한 해이므로, 별해로서 기록.

전형적인 문제이므로 새롭고 특별한 생각도 전혀 없습니다.

주제

최대 매칭으로 잘 나오는 전형적인 결혼 문제로 바꿉니다.

N명의 사람이 (이 N명과는 다른) $4*10^5$명의 상대에게 구혼하려고 하고 있습니다. $(1\leq N\leq 2*10^5)$

각 N인은 2명 $(a, b)$에 구혼한다($a=b$의 일도 있습니다).

구혼된 측은 1명과밖에 결혼할 수 없습니다.

결혼이 성립하는 최대 쌍은 몇 쌍인가?

그 밖에도 「노동자와 일」이나 「사람과 식사」등으로 바꿔 말하기도 합니다.

접근과 구현 접근

조건을 최대 매칭으로 생각합니다.



그림과 같이, 좌우에 소스 $s$와 골 $t$를 준비해, 2부 그래프의 좌측을 20만명으로 해, 우측을 40만명으로서 노드를 만듭니다. 좌측은 20만 미만의 일도 있습니다만, 변을 치지 않으면 좋을 뿐이므로, 그래프상은 처음부터 만들어 둡니다.
이때 그림과 같이 0-origin으로 생각하지 않아서 $1에서 200000$와 $200001에서 600000$로 해도 좋을 것입니다. $s$와 $t$는 적당한 노드로 합니다만, $0,1$등으로 하면 그 뒤가 2-origin가 되어(디버그할 때에) 알기 어렵기 때문에 뒤에 붙입니다.

소스 $s$에서 왼쪽의 각 노드에 1의 유량을 흘립니다. 이렇게 하면 왼쪽 노드가 오른쪽 노드에 하나만 플로우할 수 있습니다. (즉, 어느 한 쪽만 흐름을 흘릴 수 있습니다)
왼쪽의 노드로부터는 각각의 $a, b$인 오른쪽의 노드에 대해서 유량 1의 변을 늘립니다. $a=b$의 경우, 2개의 변을 쳐도 됩니다.
오른쪽 노드에서는 $t$에 대해 유량 1의 변을 늘립니다. 많은 왼쪽 노드에서 선택해도 의미는 없고, $t$에는 1 밖에 흘릴 수 없습니다.
$t$에 도달할 수 있는 플로우는, 어떠한 좌측의 노드로부터의 in이 받을 수 있는 우측의 노드의 수(각 유량은 최대 1이므로)입니다.

$s -> t$의 max-flow가 대답입니다.

구현

위의 설명대로 흐릅니다. ACL을 사용했습니다.

#include <bits/stdc++.h>
#include <atcoder/all>
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)
using namespace std;
using namespace atcoder;
const int numNode = 2*100000;
const int numColor = 4 * 100000;
const int numGraph = numNode + numColor + 100;
const int snode = numGraph - 3;
const int tnode = numGraph - 2;
int main(int argc, char *argv[]) {
    int n, a, b;
    cin >> n;
    mf_graph<int> mf(numGraph);
    REP(i, n){
        cin >> a >> b;
        a += numNode; b += numNode;
        mf.add_edge(snode, i, 1);
        mf.add_edge(i, a, 1);
        mf.add_edge(i, b, 1);
    }
    FOR(i, numNode, numNode + numColor + 2){
        mf.add_edge(i, tnode, 1);
    }
    cout << mf.flow(snode, tnode) << endl;
}