Распределение студентов по проектным группамAssigning students to project groups

Дано 3 студента (0, 1, 2) и 3 проектные группы (0, 1, 2), каждая рассчитана ровно на одного студента. Список `qualifies[i]` — множество групп, для которых у студента i достаточно навыков: студент 0 годится в группы {0, 1}, студент 1 — только в группу {0}, студент 2 — в группы {1, 2}. Нужно найти максимальное число студентов, которых можно распределить по группам так, чтобы каждый студент попал в группу, для которой он подходит, и каждая группа получила не более одного студента.Given 3 students (0, 1, 2) and 3 project groups (0, 1, 2), each sized for exactly one student. The list `qualifies[i]` is the set of groups student i has sufficient skills for: student 0 qualifies for groups {0, 1}, student 1 only for group {0}, student 2 for groups {1, 2}. Find the maximum number of students that can be assigned to groups such that each student lands in a group they qualify for, and each group gets at most one student.

// Example
qualifies = {
    0: [0, 1],
    1: [0],
    2: [1, 2]
}
// output: max_matched=3, assignment={group0: student1, group1: student0, group2: student2}

Прямое применение определения из 3.3.2: студенты — множество L, группы — множество R, ребро студент-группа существует, если студент годится по навыкам. Задача "максимум распределённых студентов" — это буквально максимальное паросочетание в этом двудольном графе.Direct application of the definition from 3.3.2: students are set L, groups are set R, a student-group edge exists if the student qualifies. "Maximum number of assigned students" is literally a maximum matching in this bipartite graph.

На первый взгляд есть подвох: и студент 0, и студент 1 годятся в группу 0, но студент 1 годится ТОЛЬКО туда — если сразу отдать группу 0 студенту 0 (первому по номеру), студент 1 останется без группы вообще, хотя решение с 3 распределениями существует. Это ровно тот сценарий, ради которого алгоритму Куна нужна увеличивающая цепь из 3.3.2: жадное присвоение "первому пришедшему" не гарантирует максимума, а поиск с возможностью "подвинуть" уже назначенного студента — гарантирует.At first glance there's a catch: both student 0 and student 1 qualify for group 0, but student 1 qualifies ONLY there — if group 0 is greedily handed to student 0 (processed first), student 1 is left with no group at all, even though a 3-assignment solution exists. This is exactly the scenario Kuhn's algorithm needs an augmenting path for, from 3.3.2: greedy "first come" assignment doesn't guarantee the maximum, but a search that can "bump" an already-assigned student does.

Пошагово, как это находит Кун: обрабатываем студента 0 первым — группа 0 свободна, назначаем 0→группа 0. Обрабатываем студента 1 — его единственный вариант, группа 0, уже занята студентом 0; вместо отказа алгоритм рекурсивно пытается пристроить студента 0 куда-то ещё — у студента 0 есть вторая опция, группа 1, она свободна — 0 переезжает в группу 1, а группа 0 освобождается для студента 1. Обрабатываем студента 2 — группа 1 занята студентом 0, но у студента 2 есть вторая опция, группа 2, она свободна — назначаем напрямую. Итог: все 3 студента распределены.Step by step, how Kuhn's algorithm finds this: process student 0 first — group 0 is free, assign 0→group 0. Process student 1 — their only option, group 0, is already taken by student 0; instead of failing, the algorithm recursively tries to place student 0 somewhere else — student 0 has a second option, group 1, which is free — 0 moves to group 1, freeing group 0 for student 1. Process student 2 — group 1 is taken by student 0, but student 2 has a second option, group 2, which is free — assign directly. Result: all 3 students are assigned.

class Solution {
    bool tryKuhn(int u, const std::vector<std::vector<int>>& adj,
                  std::vector<bool>& used, std::vector<int>& matchR) {
        for (int v : adj[u]) {
            if (used[v]) continue;
            used[v] = true;
            // группа свободна, или её текущего студента можно передвинуть// the group is free, or its current student can be moved
            if (matchR[v] == -1 || tryKuhn(matchR[v], adj, used, matchR)) {
                matchR[v] = u;
                return true;
            }
        }
        return false;
    }

public:
    std::pair<int, std::vector<int>>
    assignGroups(int numStudents, int numGroups,
                  const std::vector<std::vector<int>>& qualifies) {
        std::vector<int> matchR(numGroups, -1);  // matchR[group] = студент// matchR[group] = student
        int matched = 0;

        for (int s = 0; s < numStudents; ++s) {
            std::vector<bool> used(numGroups, false);
            if (tryKuhn(s, qualifies, used, matchR)) matched++;
        }
        return {matched, matchR};
    }
};

Сложность O(V·E) — базовая гарантия алгоритма Куна из 3.3.2: для каждого из 3 студентов запускается DFS стоимостью O(E). При таком маленьком n разница с более быстрым Хопкрофтом-Карпом (O(E√V)) незаметна — она проявляется на масштабах в сотни-тысячи студентов и групп, о чём явно предупреждал раздел "Грабли" в 3.3.2.Complexity is O(V·E) — Kuhn's algorithm's basic guarantee from 3.3.2: for each of the 3 students, a DFS costing O(E) is run. At this small n, the difference from the faster Hopcroft-Karp (O(E√V)) is invisible — it shows up at scales of hundreds to thousands of students and groups, exactly what 3.3.2's Gotchas section warned about.