We need to match as much as values from the set N with the set M. We just create a graph where every element of N is connected to every possible to match element in M. Then we run a slightly modified DFS or as some people refer to it a modified flow alrorithm. It doesn’t really matter how we call it since the flow algorithms just find as much as possible paths from the source to the sink using either BFS, DFS or PFS (priority-first search or best-first search).

In other words we just check whether an element q from N can be matched with an element t of M. If q is possible to match with t but t is matched with another element z of the set N, we check whether that element z can be matched with another element in M. If it is possible, then we can for sure make such changes that q matches t since z can match another free element in M.

We do this for every element q in N.

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int n,m; int g[201][201]; int marked[201]; int used[201]; int dfs(int k) { for (int i = 1; i<=m; ++i) { if(g[k][i]<=0) continue; used[i] = 1; if (marked[i]==-1 || dfs(marked[i])) { marked[i] = k; return 1; } } return 0; } int flow() { memset(marked,-1,sizeof(marked)); int ans = 0; for (int i = 1; i <= n; ++i) { memset(used,0,sizeof(used)); ans += dfs(i); } return ans; } int main() { FILE *in = fopen("stall4.in", "r"); fscanf(in, "%d%d", &n,&m); for (int i = 1; i<= n; ++i) { int c; int k; fscanf(in, "%d", &c); for (int z = 0; z < c; ++z) { fscanf(in, "%d", &k); g[i][k] = 1; } } fclose(in); FILE * out = fopen("stall4.out", "w"); fprintf(out, "%dn", flow()); fclose(out); return 0; }