Description
千岛是爪哇海里一组美丽的岛屿，其中有 \(N\) 个岛屿，编号为从 \(0\) 到 \(N - 1\)。
有 \(M\) 艘独木舟在岛屿之间航行，编号为从 \(0\) 到 \(M - 1\)。对于满足 \(0 \le i \le M - 1\) 的所有 \(i\)，独木舟 \(i\) 可以停靠在岛屿 \(U_i\) 或 \(V_i\)，并且在岛屿 \(U_i\) 和 \(V_i\) 之间航行。具体来说，当独木舟停靠在岛屿 \(U_i\) 时，可以用它从岛屿 \(U_i\) 去往岛屿 \(V_i\)，此后该独木舟就变成停靠在岛屿 \(V[i]\)。类似地，当该独木舟停靠在岛屿 \(V[i]\) 时，它可以从岛屿 \(V_i\) 航向岛屿 \(U_i\)，此后该独木舟就变成停靠在岛屿 \(U_i\)。在初始时，该独木舟停靠在岛屿 \(U_i\)。可能有多艘独木舟能用于在同一对岛屿之间航行。也可能会有多艘独木舟停靠在同一个岛屿处。
出于安全考虑，各艘独木舟在每次航行后必须进行维修，因此同一独木舟不允许紧接着完成两次航行。也就是说，在用完某艘独木舟 \(i\) 后，必须先用过另外某艘独木舟，才能再启用独木舟 \(i\)。
Bu Dengklek 想策划一次在部分岛屿之间的旅行。她的旅程是合理的，当且仅当满足如下条件：
- 她的旅程应从岛屿 \(0\) 开始，并且在该岛屿结束。
- 她应该游览岛屿 \(0\) 之外的至少一个岛屿。
- 在旅行结束后，每艘独木舟应停靠在旅行开始前它所在的岛屿。也就是说，对于满足 \(0 \le i \le M - 1\) 的所有 \(i\)，独木舟必须停靠在岛屿 \(U_i\)。
请你帮助 Bu Dengklek 找出包括至多航行 \(2\;000\;000\) 次的合理旅行，或者告诉她不存在合理旅行。
可以证明，在本题所给出的约束条件下（参见约束条件部分），如果存在合理旅行，则必然存在航行次数不超过 \(2\;000\;000\) 次的合理旅行。
\(N\leq 10^5,M\leq 2\times 10^5\)。
Solution
首先直接是不好构造的，考虑删点。
容易发现出度为 \(0\) 的点一定不能被经过，所以可以把这些点删掉，删掉后可能会生成新的出度为 \(0\) 的点，用拓扑排序的东西维护即可。
现在每个点的出度都至少是 \(1\) 了。如果起点 \(0\) 的出度为 \(1\)，则在走的过程中不能经过 \(0\)，可以把 \(0\) 删掉，并把起点 \(s\) 设为 \(nxt_0\)。
可以证明只要当前的 \(s\) 出度大于等于 \(2\) 则一定有解。设 \(v_1\) 是 \(s\) 第一个出边的终点，\(v_2\) 是第二个出边的终点。
如果 \(v_1\) 和 \(v_2\) 一起走可以走到同一个点 \(x\)，则可以构造成 \(s\) 先沿着 \(v_1\) 走到 \(x\)，再在 \(x\) 这里走一个环，然后走回 \(v_1\) 和 \(s\)。对 \(v_2\) 做同样的事情。（注意这里走的过程是需要动态改变边的方向的）
如果走不到同一个点，那么两个点可以走到不同的环，则 \(s\) 走 \(v_1\) 再走环回到 \(v_1\) 和 \(s\)，再走 \(v_2\) 的环，然后走 \(v_1\) 的环，再走 \(v_2\) 的环即可。
直接分讨可能细节较多，这里有一个非常优美的写法是从 \(s\) 暴力 dfs，记录上一条走的边 \(lst\)，每次枚举任意一条不是 \(lst\) 的出边走。如果当前时刻回到 \(s\) 且每条边都以达到初始状态就停止。经过手玩会发现这个写法刚好能囊括刚才的所有讨论，且细节大幅减少。
时间复杂度：\(O((N+M)\log N)\)。
Code
#include "islands.h"
#include <bits/stdc++.h>const int kMaxN = 2e5 + 5;int n, m, s, cnt;
int op[kMaxN];
std::set<std::pair<int, int>> G[kMaxN], rG[kMaxN];
std::queue<int> q;
std::vector<int> vec;
bool del[kMaxN];void topo() {for (; !q.empty(); q.pop()) {int u = q.front();if (del[u]) continue;del[u] = 1;for (auto [v, id] : rG[u]) {if (del[v]) continue;G[v].erase({u, id});if (!G[v].size()) q.emplace(v);}}
}void dfs(int u, int lst) {if (u == s && !cnt && lst != -1) return;// std::cerr << u << ' ' << lst << ' ' << cnt << '\n';for (auto [v, id] : G[u]) {if (id == lst) continue;cnt += (!op[id] ? 1 : -1), op[id] ^= 1, vec.emplace_back(id);G[u].erase({v, id}), G[v].emplace(u, id);return dfs(v, id);}
}std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {n = N, m = M;for (int i = 0; i < m; ++i) {op[i] = 0, G[U[i]].emplace(V[i], i), rG[V[i]].emplace(U[i], i);}for (int i = 0; i < n; ++i)if (!G[i].size())q.emplace(i);topo();// std::cerr << s << ' ' << G[s].size() << '\n';s = 0;std::vector<int> tmp;for (; G[s].size() == 1;) {auto [nxt, id] = *G[s].begin();// std::cerr << "shabi " << s << ' ' << nxt << ' ' << id << '\n';q.emplace(s), tmp.emplace_back(id), s = nxt;topo();}if (!G[s].size() || del[s]) return false;for (int i = 0; i < n; ++i) {for (; G[i].size() > (i == s) + 1; G[i].erase(G[i].begin())) {}}dfs(s, -1);std::vector<int> res = tmp;for (auto x : vec) res.emplace_back(x);std::reverse(tmp.begin(), tmp.end());for (auto x : tmp) res.emplace_back(x);// std::cerr << "??? " << tmp[0] << ' ' << res[0] << '\n';// for (auto x : res) std::cerr << x << ' ';// std::cerr << '\n';return res;
}
)
