[UVa] 10092 - The Problem with the Problem Setter

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10092 - The Problem with the Problem Setter
Source            : UVa Online Judge
Category          : Graph Theory
Algorithm         : Maximum Bipartite Matching, Hopcropt Carp Algorithm
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
#define inf           1 << 28
#define NILL          0
 
static const int MAXN = 1e4 + 5;
 
vector <int> graph[MAXN];
 
int m; // no.of elements in left side
int n; // no.of elements in right side
 
int pairU[MAXN],
    pairV[MAXN],
    dist[MAXN];
 
 
bool bfs()
{
    queue <int> PQ;
    for (int u = 1; u <= m; u++)
    {
        if (pairU[u] == NILL)
        {
            dist[u] = NILL;
            PQ.push(u);
        }
        else
        {
            dist[u] = inf;
        }
    }
    dist[NILL] = inf;
    while (!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        if (u != NILL && dist[u] < dist[NILL])
        {
            for (int v : graph[u])
            {
                if (dist[ pairV[v] ] == inf)
                {
                    dist[ pairV[v] ] = dist[u] + 1;
                    PQ.push(pairV[v]);
                }
            }
        }
    }
    if (dist[NILL] != inf) return true;
    else return false;
}
 
bool dfs(int u)
{
    if (u != NILL)
    {
        for (int v : graph[u])
        {
            if (dist[ pairV[v] ] == dist[u] + 1)
            {
                if (dfs(pairV[v]))
                {
                    pairU[u] = v;
                    pairV[v] = u;
                    return true;
                }
            }
        }
        dist[u] = inf;
        return false;
    }
    return true;
}
 
int hopcropt_carp()
{
    int max_match = 0;
    while (bfs())
    {
        for (int u = 1; u <= m; u++)
        {
            if (pairU[u] == NILL && dfs(u))
            {
                max_match++;
            }
        }
    }
    return max_match;
}
 
int cntCategory[22];
int start[22];
 
int main()
{
    //freopen("input.txt", "r", stdin);
 
    int category, problem;
    while (scanf("%d %d", &category, &problem) == 2)
    {
 
        if (category+problem == 0) break;
        m = 0;
        n = problem;
        for (int i = 1; i <= category; i++)
        {
            scanf("%d", &cntCategory[i]);
            start[i] = m+1;
            m += cntCategory[i];
        }
        for (int v = 1; v <= problem; v++)
        {
            int x;
            scanf("%d", &x);
            for (int i = 0; i < x; i++)
            {
                int c;
                scanf("%d", &c);
                for (int j = 0; j < cntCategory[c]; j++)
                {
                    int u = j + start[c];
                    graph[u].push_back(v + m);
                    graph[v + m].push_back(u);
                }
            }
        }
        int match = hopcropt_carp();
        //printf("%d\n", match);
        if (match != m)
        {
            puts("0");
        }
        else
        {
            puts("1");
            for (int i = 1; i <= category; i++)
            {
                for (int j = 0; j < cntCategory[i]; j++)
                {
                    printf("%d", pairU[ j + start[i] ] - m);
                    if (j+1 == cntCategory[i]) puts("");
                    else printf(" ");
                }
            }
        }
        memset(pairU, NILL, sizeof pairU);
        memset(pairV, NILL, sizeof pairV);
        for (int i = 0; i < MAXN; i++)
            graph[i].clear();
    }
}