LOJ #3835. 「IOI2022」千岛 题解

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;
}