[C++] 단방향 링크 네트워크 (백준 3295번)

https://www.acmicpc.net/problem/3295

 

그래프의 구조가 링이거나 선형 배열이라는 것은 그래프를 이루는 각 노드들의 in-degree도 최대 1이고 out-degree도 최대 1이라는 것이다.

 

그리고 k개의 노드로 이루어진 링의 가치가 k이고 k개의 노드로 이루어진 선형 배열의 가치가 k라는 것은 어떤 그래프에서 각 노드의 in-degree도 최대 1이고 out-degree도 최대 1이 되도록 간선들을 선택했을 때의 간선 개수 자체가 가치가 된다는 뜻이다.

 

따라서 왼쪽에 출발  노드 집합을 두고 오른쪽에 도착 노드 집합을 두고 최대 이분 매칭을 구하면 된다.

 

// Reference: green55 teamnote
// https://github.com/green5555/Teamnote/blob/master/TeamNote/BiMatch.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAX = 2000;
struct BiMatching {
    vector<int> adj[MAX+5];
    int iter, A[MAX+5], B[MAX+5], was[MAX+5];

    bool dfs(int u) {
        was[u] = iter;
        for (int v : adj[u]) {
            if (B[v] == -1) {
                A[u] = v;
                B[v] = u;
                return true;
            }
        }
        for (int v : adj[u]) {
            if (was[B[v]] != iter && dfs(B[v])) {
                A[u] = v;
                B[v] = u;
                return true;
            }
        }
        return false;
    }

    int biMatch(int n=MAX) {
        fill(A, A+n, -1);
        fill(B, B+n, -1);
        fill(was, was+n, 0);
        iter = 0;
        int res = 0;
        while (true) {
            iter++;
            int add = 0;
            for (int i = 0; i < n; i++) {
                if (A[i] == -1 && dfs(i)) {
                    add++;
                }
            }
            if (add == 0) {
                break;
            }
            res += add;
        }
        return res;
    }
};

void solve() {
    BiMatching bm;

    int n, m;
    cin >> n >> m;

    while (m--) {
        int a, b;
        cin >> a >> b;
        bm.adj[a].push_back(b + 1000);
    }

    cout << bm.biMatch() << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)