HDU1054+最小顶点覆盖

/*
最小顶点覆盖：选出最少的点，这些点的关联的边都被覆盖
最小顶点覆盖等于最大匹配

*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<math.h>
using namespace std;
const int maxn = 1505;
const int inf = 0x7fffffff;
struct node{
    int u,val,next;
}edge[ maxn<<2 ];
int head[ maxn ],vis[ maxn ],fa[ maxn ];
int cnt;
void init(){
    memset( head,-1,sizeof(vis) );
    memset( fa,-1,sizeof(fa) );
    cnt=0;
}
void addedge( int a,int b,int c ){
    edge[ cnt ].u=b;
    edge[ cnt ].val=c;
    edge[ cnt ].next=head[ a ];
    head[ a ]=cnt++;
}

int dfs( int x ){
//    int u=head[ x ];
    for( int i=head[ x ];i!=-1;i=edge[i].next ){
        int u=edge[ i ].u;
        if( vis[ u ]==0 ){
            vis[ u ]=1;
            if( fa[ u ]==-1 || dfs( fa[u] ) ){
                fa[ u ]=x;
                return 1;
            }
        }
    }
    return 0;
}
            
int main(){
    int n;
    while( scanf("%d",&n)!=EOF ){
        char s[ 2001 ];
        init();
        for( int i=0;i<n;i++ ){
            int a,b,c;
            int tmp;
            scanf("%d:(%d)",&a,&tmp);
            while( tmp-- ){
                scanf("%d",&b);
                addedge( a,b,1 );
                addedge( b,a,1 );
            }
        }
        int ans=0;
        for( int i=0;i<n;i++ ){
            if( head[ i ]==-1 ) continue;
            memset( vis,0,sizeof(vis) );
            ans+=dfs( i );
        }
        printf("%d\n",ans/2);
    }
    return 0;
}