题目链接

http://poj.org/problem?id=1469

解题思路

二分图匹配
提醒一下，cin好像TLE

AC代码

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=400;
vector<int> e[N];
int n,m,cnt,u,num,link[N],vis[N],T;

bool dfs(int x)
{
    for(int i=0;i<e[x].size();i++)
    {
        int v=e[x][i];
        if(vis[v]) continue;
        vis[v]=1;
        if(link[v]==0 || dfs(link[v]))
        {
            link[v]=x;
            return 1;
        }
    }
    return 0;
}

int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(link,0,sizeof link);
        for(int i=1;i<=n;i++) e[i].clear();

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num);
            while(num--) scanf("%d",&u),e[i].push_back(u);
        }

        int i;
        for(i=1;i<=n;i++)
        {
            memset(vis,0,sizeof vis);
            if(!dfs(i)) break;
        }
        if(i==n+1) puts("YES");
        else puts("NO");
    }
}