题解 - QOJ 8757 图

绝好题。

简述题意

给一个 $n$ 点 $m$ 边无向图，可能存在重边，不存在自环。令 $k=\lceil \frac{m}{n-1} \rceil$，找出点 $u,v(u\neq v)$，输出 $u\to v$ 的 $k$ 条边不交路径。无解输出 -1。

多测。$\sum n\le 10^5$，$\sum m\le 2\times 10^5$。

分析

看见 $n-1$ 想到树是当然的，但是如何进一步拓展是困难的。

观察样例，猜想是必然存在，而且 $k$ 正好是上界。考虑 $u\to v$ 的路径有至少 $k$ 条。且由题，$\frac{m}{n-1}\le k<\frac{m+n-1}{n-1}$，如果纠结在取等的不等号，则有点使人疑惑。

另一个有关于树的结论是：一棵树上，任意两点间有唯一路径。

那么，能否构造若干个森林，使得在每个森林里，$u,v$ 都联通，然后在每个森林都找出 $u\to v$ 的路径？

那么一种自然的想法是，让每对 $(u,v)$ 都在一段前缀森林中联通。这样，对每个边我们从前往后逐个尝试加入并查集中即可。事实上，这个过程可以二分优化。

下面，我们要证明这个结论的正确性。

如果可能找不到，那么最后一个森林中一条边也没有。而前面的 $k-1$ 个森林中，至多有 $(k-1)(n-1)$ 条边，根据 $k(n-1)<m+n-1$，$(k-1)(n-1)<m$，即必有富余的边会考虑加入第 $k$ 个森林。所以最后一个森林中必有边。这启示我们，面对取整符号，两端都要留意。

时间复杂度 $O(n\log m\alpha (n))$，实现不精细，两只 $\log$ 也可以了。空间复杂度 $O(m)$。

代码

#include <bits/stdc++.h>
using namespace std;

int find(vector<int>& fa, int x) {
  return ~fa[x] ? fa[x] = find(fa, fa[x]) : x;
}

int main() {
  int T(0);
  cin >> T;
  while (T--) {
    int N(0), M(0);
    cin >> N >> M;
    int cnt(ceil(M * 1.0 / (N - 1)));
    vector<vector<int>> dsets(cnt, vector<int>(N, -1));
    vector<vector<vector<int>>> tos(cnt, vector<vector<int>>(N));
    for (int x(0), y(0); M--;) {
      cin >> x >> y;
      --x, --y;
      int l(-1), r(cnt - 1);
      while (r - l > 1) {
        int m((l + r) >> 1);
        if (find(dsets[m], x) != find(dsets[m], y))
          r = m;
        else
          l = m;
      }
      int a(find(dsets[r], x)), b(find(dsets[r], y));
      if (a != b) {
        tos[r][x].push_back(y);
        tos[r][y].push_back(x);
        dsets[r][a] = b;
      }
    }
    int u(0);
    for (; u != N && dsets[cnt - 1][u] == -1; ++u);
    assert(u != N);
    int v(dsets[cnt - 1][u]);
    cout << u + 1 << ' ' << v + 1 << endl;
    for (int id(0); id != cnt; ++id) {
      vector<int> pre(N, -1);
      deque<int> que;
      que.push_back(v);
      while (!que.empty()) {
        int c(que.front());
        que.pop_front();
        for (auto p : tos[id][c]) {
          if (pre[p] == -1 && p != v)
            pre[p] = c, que.push_back(p);
        }
      }
      int len(0);
      for (int i(u); ~i; i = pre[i]) ++len;
      cout << len;
      for (int i(u); ~i; i = pre[i]) cout << ' ' << i + 1;
      cout << endl;
    }
  }
  return 0;
}