poj 1469 COURSES (最大匹配)

題目意思:

有N個學生和P門課程，讓你判斷能否構成最大匹配。

先輸入一個T，表示有T組測試數據；

在輸入N和P，P表示有P門課程，N表示有N個學生。

之後有P行，比如：

a  a1 a2 a3 a4 a5---第一行。1與a1,a2,a3,a4,a5有匹配。

b b1 b2 b3-----第二行。b與b1,b2,b3有匹配。

如果匹配數等於學生數目則YES；

否則為NO；

[cpp]
#include"stdio.h" 
#include"string.h" 
#define N 501 
int n,m,map[N][N],mark[N],link[N]; 
int dfs(int t) 
{ 
    int i; 
    for(i=1;i<=m;i++) 
    { 
        if(!mark[i]&&map[t][i]) 
        { 
            mark[i]=1; 
            if(link[i]==-1||dfs(link[i])) 
            { 
                link[i]=t; 
                return 1; 
            } 
        } 
    } 
    return 0; 
} 
int MaxMatch() 
{ 
    int i,num; 
    num=0; 
    memset(link,-1,sizeof(link)); 
    for(i=1;i<=m;i++) 
    { 
        memset(mark,0,sizeof(mark)); 
        if(dfs(i)) 
            num++; 
    } 
    return num; 
} 
int main() 
{ 
    int i,j,a,b,T,ans; 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%d%d",&n,&m); 
        memset(map,0,sizeof(map)); 
        for(i=1;i<=n;i++) 
        { 
            scanf("%d",&a); 
            for(j=0;j<a;j++) 
            { 
                scanf("%d",&b); 
                map[i][b]=1; 
            } 
        } 
        ans=MaxMatch(); 
        //printf("%d\n",ans); 
        if(MaxMatch()==n) 
            printf("YES\n"); 
        else 
            printf("NO\n"); 
    } 
    return 0; 
}