给定一张 个点 条边的有向无环图，定点编号从 到 ，对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第 小的路径。保证存在至少 条路径。上述参数满足 。
在程序中，我们求出从每个点出发的路径数量。超过 的数都用 表示。然后我们根据 的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。
试补全程序。
#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 100000;
const long long LIM = 1000000000000000000ll;
int n, m, deg[MAXN];
std::vector<int> E[MAXN];
long long k, f[MAXN];
int next(std::vector<int> cand, long long &k) {
std::sort(cand.begin(), cand.end());
for (int u : cand) {
if (①) return u;
k -= f[u];
}
return -1;
}
int main() {
std::cin >> n >> m >> k;
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v; // 一条从u到v的边
E[u].push_back(v);
++deg[v];
}
std::vector<int> Q;
for (int i = 0; i < n; ++i)
if (!deg[i]) Q.push_back(i);
for (int i = 0; i < n; ++i) {
int u = Q[i];
for (int v : E[u]) {
if (②)
Q.push_back(v);
--deg[v];
}
}
std::reverse(Q.begin(), Q.end());
for (int u : Q) {
f[u] = 1;
for (int v : E[u])
f[u] = ③;
}
int u = next(Q, k);
std::cout << u << std::endl;
while (④) {
⑤;
u = next(E[u], k);
std::cout << u << std::endl;
}
return 0;
}