백준2188 축사 배정 - C++

소가 들어가고 싶은 축사가 정해져있고, 한 축사에 한 마리씩 넣으면 된다.
최대유량이나 이분매칭으로 구하면 된다.
 
훨씬 간단한 이분매칭으로 풀었다.
 
소 그룹을 A, 축사 그룹을 B 라고 뒀을 때,
소 3마리, 축사 4개가 있고
S1 = [ 1, 2, 3 ]
S2 = [ 1, 2, 3, 4 ]
S3 = [ 2, 3, 4 ]
일 때를 생각해보자. 
그럼 그래프를 다음과 같이 그릴 수 있다.

소 1번부터 차례대로 원하는 축사를 고른다고 생각해보자.
1번 소가 1번 축사를 고른다.
 
그 후 2번 소가 고를 차롄데 2번 소도 1번을 가고 싶다.
그럼 2번 소를 1번 축사에 넣고
1번 소를 1번이 아닌 다른 가고 싶은 축사 2번에 넣는다.
 
그 후 3번 소가 고를 차롄데 3번 소는 2번이 가고 싶다.
3번 소를 2번에 넣고, 2번에 있던 1번 소를 1, 2 가 아닌 다른 가고 싶은 축사 3번에 넣는다.
 
이런 식으로 밀어내는 식으로 만들게 되면 
앞선 소부터 차례대로 최대 유량을 만들 수 있고(사실 MCMF와 동일하다)
최대 유량이 소가 축사에 들어가는 최대 수이므로 답이 나온다.(보장된다)
 

#include<iostream>
#include<vector>
#include <cstring>
using namespace std;

const int MAXN = 201;
vector<int> adjlist[MAXN];
int matched[201];
bool visited[201];

int N, M;


bool bimatch(int x) {
	for (int i = 0; i < adjlist[x].size(); i++)
	{
		int a = adjlist[x][i];
		if (visited[a]) continue;
		visited[a] = true;
		if (matched[a] == 0 || bimatch(matched[a]))
		{
			matched[a] = x;
			return true;
		}
	}
	return false;
}
int main()
{
	int cnt=0;
    int S;
    int want;
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		cin >> S
		for (int j = 0; j < S; j++)
		{
			cin >> want;
			adjlist[i].push_back(want);

		}
	}

	for (int i = 1; i <= N; i++)
	{
        memset(visited, 0, sizeof(visited));
		if (bimatch(i)) cnt++;
	}

	cout << cnt;
    return 0;
}