열혈강호 - 11375

//11375 - 열혈강호
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
vector<vector<bool>> adj;
vector<int> aMatch, bMatch;
vector<bool> visited;
 
void init()
{
    cin >> N >> M;
    adj = vector<vector<bool>>(N + 1, vector<bool>(M + 1, false));
    int n;
    int from;
    for(int to = 1; to<=N; ++to)
    {
        cin >> n;
        for(int i = 0; i<n; ++i)
        {
            cin >> from;
            adj[to][from] = true;
        }
    }
}
 
bool dfs(int here)
{
    if(visited[here]) return false;
    visited[here] = true;
    for(int there = 1; there<=M; ++there)
        if(adj[here][there])
            if(bMatch[there] == -1 || dfs(bMatch[there]))
            {
                aMatch[here] = there;
                bMatch[there] = here;
                return true;
            }
    return false;
}
 
int bipartiteMatch()
{
    aMatch = vector<int>(N+1, -1);
    bMatch = vector<int>(M+1, -1);
    int ret = 0;
    for(int i = 1; i<=N; ++i)
    {
        visited = vector<bool>(N+1, false);
        if(dfs(i))
            ++ret;
    }
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    cout << bipartiteMatch();
}

 

 

 

 

 

 

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

11375번: 열혈강호

 

 

 

 

 

 

열혈강호

이분매칭을 해결하기 위한 간략한 ford-fulkerson 알고리즘을 사용했습니다.