백준 3295번: 단방향 링크 네트워크

문제링크

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

3295번: 단방향 링크 네트워크

풀이

• 구조의 가치는 구조를 이루는 간선의 수이다.
• 링 또는 선형으로만 구성되어있다는 것은 한 정점에서 나가는 간선, 들어오는 간선은 최대 1개씩 있을 수 있다는 뜻
• 간선의 시작점, 도착점 두 그룹으로 이분매칭

코드

• 시간복잡도: $O(VE) = O(NM)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

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

    int TC; cin >> TC;
    while (TC--) {
        int N, M;
        cin >> N >> M;

        vector<vector<int> > adj(N);
        vector<int> B(N, -1);

        for (int i = 0; i < M; ++i) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
        }
        vector<int> visited(N, 0);
        function<bool(int)> f = [&](int a) {
            visited[a] = true;
            for (auto b: adj[a]) {
                if (B[b] == -1 || (!visited[B[b]] && f(B[b]))) {
                    B[b] = a;
                    return true;
                }
            }
            return false;
        };

        long long ans = 0;
        for (int i = 0; i < N; ++i) {
            fill(all(visited), false);
            ans += f(i);
        }
        cout << ans << '\n';
    }
}