POJ 1469 COURSES (二分图最大匹配 匈牙利算法)

• every student in the committee represents a different course (a student can represent a course if he/she visits that course)
  
• each course has a representative in the committee
  

#include <cstdio>
#include <cstring>
bool g[105][305];
int cx[105], cy[305];
bool vis[305];
int n, p;

int DFS(int x)
{
    for(int y = 1; y <= n; y++)
    {
        if(!vis[y] && g[x][y])
        {
            vis[y] = true;
            if(cy[y] == -1 || DFS(cy[y]))
            {
                cx[x] = y;
                cy[y] = x;
                return 1;
            }
        }
    }
    return 0;
}

int MaxMatch()
{
    int res = 0;
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    for(int i = 1; i <= p; i++)
    {
        if(cx[i] == -1)
        {
            memset(vis, false, sizeof(vis));
            res += DFS(i);
        }
    }
    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        memset(g, false, sizeof(g));
        scanf("%d %d", &p, &n);
        for(int i = 1; i <= p; i++)
        {
            int cnt;
            scanf("%d", &cnt);
            while(cnt --)
            {
                int j;
                scanf("%d", &j);
                g[i][j] = true;
            }
        }
        int ans = MaxMatch();
        if(ans == p)
            printf("YES\n");
        else
            printf("NO\n");
    }
}