hdu1054
코드:
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#define maxn 1505
using namespace std;
vector<int> g[maxn];
int vis[maxn];
int link[maxn];
bool getnum(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!vis[v])
{
vis[v]=1;
if(link[v]==-1||getnum(link[v]))
{
link[v]=u;
return true;
}
}
}
return false;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int u,m,v;
for(int i=0;i<n;i++)
{
g[i].clear();
}
for(int i=0;i<n;i++)
{
scanf("%d:(%d)",&u,&m);
for(int j=0;j<m;j++)
{
scanf("%d",&v);
g[u].push_back(v);
g[v].push_back(u);
}
}
memset(link,-1,sizeof(link));
int count=0;
for(int i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));//
if(getnum(i))
count++;
}
printf("%d
",count/2);
}
return 0;
}