想当难的一道状压dp题。
首先这道题拓扑排序是错误的，因为拓扑只能保证找到选出一种上完所有课的方式，而不能保证选出的方式是所有方式中需要学期数最少的。
当然可以通过遍历所有的拓扑路径，然后取其最小学期数的路径作为答案，这是一种做法。
正解是使用状压dp，将学过的课程按照其编号-1置二进制串S的对应位为1，这样就可以用S来表示学过的课程集合。
定义f[i]表示状态为i需要学习的最少学期数，need[i]表示状态为i需要学习的前置课程集合。
首先考虑need的状态转移，我们枚举状态通常是从小到大枚举，所以推理出一个新的状态对应的need值可以用先前已经得到的小的状态的need值。我们可以取状态i的任意一个子集sub（由于sub是i的子集，所以值必然已经被计算出了）。显然状态i的前置课程就是子集sub的前置课程和去掉子集sub剩下的部分的前置课程的并集。所以有need[i] = need[sub] | need[i ^ sub]，其中i ^ sub表示状态i去掉子集sub后剩下的那部分。为了方便，我们每次都取sub为lowbit(i)。
最后考虑f的状态转移，对于状态i，可以得到对应需要学习的集合i ^ need[i]。如果该集合的课程数小于k，那么可以一次性全部学习掉，否则，枚举该集合的子集sub，f[i] = min(f[i ^ sub] + 1)。即，学哪个子集，可以让答案最小，就选哪个。
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
vector<int> f(1 << n, INT_MAX);
vector<int> need(1 << n, 0);
// 编号从0开始
for (auto &relation : relations) {
need[1 << (relation[1] - 1)] |= 1 << (relation[0] - 1);
}
f[0] = 0;
for (int i = 1; i < 1 << n; ++i)
{
int sub = i & -i;
need[i] = need[i ^ sub] | need[sub];
if ((need[i] | i) != i) continue; // i集合内有课程未完成
int valid = i ^ need[i]; // 可以学习哪些课程
if (__builtin_popcount(valid) <= k) f[i] = min(f[i], f[i ^ valid] + 1);
else
for (int sub = valid; sub; sub = (sub - 1) & valid)
if (__builtin_popcount(sub) <= k)
f[i] = min(f[i], f[i ^ sub] + 1);
}
return f[(1 << n) - 1];
}
};