백준[11375] 열혈강호

문제 설명

문제 링크

http://icpc.me/11375

11375번: 열혈강호

풀이

이분 매칭 연습문제다.

백준 2188 축사배정을 풀었다면 날먹문제다. 배열 크기만 바꿔서 제출하면 맞을 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1003;
vector<int> v[N];
bool visited[N]; // 왼쪽 집합의 i를 방문했는지 여부
int r[N]; // 오른쪽 집합의  i가 연결된 놈

bool dfs(int a) {
    visited[a] = true;
    for (auto b : v[a]) {
        // b가 연결된게 없거나, b에 이미 연결된 놈을 방문 안했고, dfs로 들어가면 이미 연결된놈을 방문처리 해서 건너뛰고 다른놈에 연결
        if (r[b] == -1 || !visited[r[b]] && dfs(r[b])) {
            r[b] = a;
            return true;
        }
    }
    return false;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int s; cin >> s;
        v[i].resize(s);
        for (auto &k : v[i]) cin >> k;
    }
    fill(r, r + N, -1);
    
    int ret = 0;
    for (int i = 0; i < n; i++) {
        fill(visited, visited + N, false);
        if (dfs(i)) ret++;
    }
    
    cout << ret;
}