Model
There are N workers and M jobs. Each worker lists the jobs they can do. Assign each job to at most one worker, and assign at most two jobs to each worker; maximize the number of assigned jobs.
Make a bipartite graph with two matching slots for each worker. Connect both slots to exactly the jobs that worker can do. A matching uses each slot and each job at most once, so a worker receives at most two jobs and no job is assigned twice. Conversely, any valid assignment can place a worker’s two (or fewer) assigned jobs into their two slots. Thus the maximum matching size is exactly the desired answer.
Augmenting paths
Process every slot with a standard augmenting-path search. For one search, mark jobs rather than slots. When a candidate job is already matched, recursively try to move its current slot to another eligible job. If that succeeds, give the candidate job to the current slot. A job is visited at most once in a search, which prevents cycles; successful reassignment preserves the matching invariant. By the augmenting-path theorem, processing all left-side slots this way produces a maximum matching.
There are 2N slots and E worker-job eligibility edges (counted once per worker). One DFS takes O(E) time, so the total time is O(N E). The graph and matching arrays use O(N + M + E) space.
C++17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> jobs(n);
for (int worker = 0; worker < n; ++worker) {
int count;
cin >> count;
jobs[worker].resize(count);
for (int& job : jobs[worker]) {
cin >> job;
--job;
}
}
// matchedSlot[job] is the slot currently assigned to this job.
vector<int> matchedSlot(m, -1);
vector<char> visitedJob(m);
auto augment = [&](auto&& self, int slot) -> bool {
for (int job : jobs[slot / 2]) {
if (visitedJob[job]) continue;
visitedJob[job] = true;
if (matchedSlot[job] == -1 ||
self(self, matchedSlot[job])) {
matchedSlot[job] = slot;
return true;
}
}
return false;
};
int assigned = 0;
for (int slot = 0; slot < 2 * n; ++slot) {
fill(visitedJob.begin(), visitedJob.end(), false);
if (augment(augment, slot)) ++assigned;
}
cout << assigned << '\n';
return 0;
}
The recursion only changes ownership along an augmenting path, so each successful search increases the matching by exactly one while keeping every job and slot unique.