[ 문제 ] 매점

매점.Zip

0.01MB

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include<iostream>
using namespace std;
int mp[500][500];
int check[500];
int n,m,ans=0,d;
void f(int x)
{
	if(x==n+m)
	{
		d=1;
		return;
	}
	for(int i=0;i<=n+m;i++)
	{
		if(mp[x][i]==1 && check[i]==0)
		{
			check[i]=1;
			f(i);
			if(d==1)
			{
				mp[x][i]=0;
				mp[i][x]=1;
				check[i]=0;
				break;
			}
		}
	}
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int c,a,i,j;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
		cin>>c;
		for(j=0;j<c;j++)
		{
			cin>>a;
			mp[i][n+a-1]=1;
		}
	}
	for(i=n;i<n+m;i++)
	{
		mp[i][n+m]=1;
	}
	for(i=0;i<n;i++)
	{
		d=0;
		f(i);
		if(d==1)
		{
			ans++;
		}
		for(j=0;j<=n+m;j++)
		{
			check[j]=0;
		}
	}
	cout<<ans<<'\n';
	return 0;
}