题目链接：https://codeforces.com/problemset/problem/1912/H
题意
有 \(n\) 个城市，\(m\) 个人。第 \(i\) 人想从城市 \(a_i\) 移动到 \(b_i\)。每个城市每天可以使用至多一次传送胶囊，可以将任意数目的人从该城市传送到任意一个（相同的）其它城市。注意传送有时间顺序。
求是否可以让所有人到达目的地。如果可以达到，给出使用传送胶囊最少的传送方案，输出每个传送胶囊的起终点。\(n \le 10^3, m \le 10^5\)。
题解（官解）
这题很有意思，但是官解讲的有点不清晰，我尽量添加一些细节，包括一些关键结论的证明。而且这个数据范围也有些迷惑，我还以为会是 \(O(m + n^2)\) 之类的时间复杂度。
如果有合适的传送方案，以传送方案为边建图 \(T\)，则显然每个连通片是树或基环树。
结论 \(1\)：如果存在方案，存在一种方案，使每个连通片是链或环。
证明：只要存在形如 \(a \to c, b \to c\) 的连边，将其改为 \(a \to b \to c\)，\(a \to b\) 在 \(b \to c\) 之前发生，原来可行的方案一定仍然可行。不断进行这样的调整，树和基环树最终被调整为链或环。
有了这个结论我们可以把操作的时间顺序固定下来。对链显然时间顺序等于边的顺序最优；对环从一个起点绕环一圈的时间顺序最优。注意由于有时间顺序的限制，环其实是假的环，相当于起点 \(u\) 可以到达其它所有点，外加一条链。
以每个人的源和目的建图 \(G\)。
结论 \(2\)：最优方案中，\(T\) 的每个连通片（弱连通分量）的点集和 \(G\) 相同。
证明：首先显然每个 \(G\) 的连通片必须在 \(T\) 中连通。如果 \(G\) 中的两个连通片在 \(T\) 中连通，若为链则一定可以分开为两条链（按照时间顺序重新连接两条链即可）；若为环也一定可以分成两个环（同样按照时间顺序重新连接两个环）。
有了这两个结论，我们就可以分开 \(G\) 的每个连通片考虑。
如果这个连通片无环，则按照拓扑序指定一条链。拓扑序保证了每个人终点在起点之后可达。否则，需要指定一个环。枚举每个点 \(u\) 作为环的起点。由关于时间顺序的说明，如果存在方案使得点 \(u\) 作为环的起点，该连通片除去从 \(u\) 出发的所有边一定是无环的。构造这部分的一条链，加上点 \(u\) 作为起点组成环就是答案。如果任意一个点都不能作为起点，无解。
时间复杂度 \(O(n(n + m))\)。
代码实现（C++）
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> uadj(n), adj(n);
for (int ei = 0; ei < m; ei++) {
int u, v;
cin >> u >> v;
u--, v--;
uadj[u].push_back(v), uadj[v].push_back(u);
adj[u].push_back(v);
}
vector<int> vis(n);
vector<vector<int>> comp;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
comp.push_back({});
queue<int> q;
vis[i] = true;
q.push(i);
while (q.size()) {
int u = q.front();
q.pop();
comp.back().push_back(u);
for (int v : uadj[u]) {
if (!vis[v]) vis[v] = 1, q.push(v);
}
}
}
}
vector<pair<int, int>> ans;
auto topo_order = [&](const auto &vec) -> vector<int> {
vector<int> in_deg(n);
for (int u : vec)
for (int v : adj[u])
in_deg[v]++;
queue<int> q;
for (int u : vec) {
if (!in_deg[u]) { q.push(u); }
}
vector<int> res;
while (q.size()) {
int u = q.front();
q.pop();
res.push_back(u);
for (int v : adj[u]) {
if (!--in_deg[v]) q.push(v);
}
}
return res;
};
auto handle_cyclic = [&](auto &vec) {
for (int u : vec) {
auto adju = std::move(adj[u]);
vector<int> res = topo_order(vec);
if (res.size() == vec.size()) {
res.erase(ranges::find(res, u));
ans.push_back({u, res[0]});
for (int i = 0; i < (int)res.size() - 1; i++)
ans.push_back({res[i], res[i + 1]});
ans.push_back({res.back(), u});
return;
}
adj[u] = std::move(adju);
}
cout << -1 << "\n";
exit(0);
};
for (auto vec : comp) {
if (auto res = topo_order(vec); res.size() == vec.size()) {
for (int i = 0; i < (int)res.size() - 1; i++)
ans.push_back({res[i], res[i + 1]});
} else {
handle_cyclic(vec);
}
}
cout << ans.size() << "\n";
for (auto [u, v] : ans)
cout << u + 1 << " " << v + 1 << "\n";
}