P10247 Pairing Pairs 题解

tiger2005 · 2024-03-10 21:04:02 · 题解

首先考虑对每个数对 (x, y)，在某个图上将点 x 和点 y 连在一起，那么读入的信息就转换到了图上，限制也变成了选择的边不“点相邻”。我们将要借助这个图论述一个重要性质：答案要么全是 0，要么只有不超过三个 0。

证明：假设有一个数对 (a, b) 答案是 0，那么这代表了所有的边都和 a 或者 b 相连。首先，如果所有的边都连向了同一个点，那么自然每条边都和其他的边相邻，自然答案就都是 0。否则，假设一些边 u \in S 挂在了 a 点下，一些边 v \in T 挂在了 b 点下。考虑到三元环处理起来比较棘手，我们来专门论述这种情况：

这张图不存在包含 (a, b) 的三元环，那么只需要随便找一个 u_0 \in S 匹配 T 集合的所有点，反之亦然。

这张图存在恰好一个包含 (a, b) 的三元环（假设第三个点是 c），那么图的形状变成了一个深度为 2 的基环树，其中两个节点 a, b 下挂了一些边。紧接着注意到这些边实际上都一定有答案，比如挂在 a 点下的边就可以将 (b, c) 作为答案，那么唯一有可能没有答案的就是三元环上的三条边。最劣情况自然就是 m=3 时，三条边都没有答案，此时就达到了答案中 0 个数的最大值。

这张图存在超过一个包含 (a, b) 的三元环，那么它们自然形成了至少一个四元环（比如 a - c - b - d - a ）。注意到四元环中每一条边都可以将对边作为答案，我们就可以利用 (a, c) 和 (b, d) 更新其他所有边的答案。具体方式参考 (1.)。

在这个性质的保证下，我们可以用极为暴力的方式在 O(n+m) 的正确复杂度下完成这道题目。

首先，将每个点的度数记下，判断是否是菊花图的情况；
其次，按顺序枚举每条边并暴力找答案，直到找到了一组或者确定无解。我们理论上只需要枚举四次就能找到一组答案，而由于此时无解的情况只可能是整张图只有一个三元环，那么复杂度自然是正确的。
最后，假设我们找到了一组答案 s = (a, b) 和 t = (c, d)，那么我们枚举其他所有的边，并优先将它们和这两条边匹配。如果一条边同时和这两条边相邻，那么其必然是一边接在 a / b 上，一边接在 c / d 上，只有 4 种情况，那么我们只需要对它们进行暴力查找即可。

int main() {
  int n, m; cin >> m >> n;
  vector<pair<int, int>> vp(n);
  vector<int> deg(m + 1);
  for (auto &[a, b]: vp)
    cin >> a >> b, ++ deg[a], ++ deg[b];

  for (int i = 1; i <= m; i ++) if (deg[i] == n) {
    for (int j = 0; j < n; j ++)
      printf("0 ");
    return 0;
  }

  vector<int> ans(n, -1);
  auto check = [&] (int i, int j) {
    auto [a, b] = vp[i];
    auto [c, d] = vp[j];
    return (a != c && a != d && b != c && b != d);
  };

  int s = 0, t = -1;
  while (s < n) {
    for (int i = s + 1; i < n; i ++)
      if (check(i, s))
        t = i;
    if (t != -1)
      break;
    ++ s;
  }

  if (s == n) {
    for (int j = 0; j < n; j ++)
      printf("0 ");
    return 0;
  }

  for (int i = 0; i < n; i ++) {
    if (check(s, i))
      ans[i] = s;
    else if (check(t, i))
      ans[i] = t;
    else {
      for (int j = 0; j < n; j ++) if (check(i, j))
        ans[i] = j;
    }
  }

  for (auto e: ans)
    cout << e + 1 << ' ';

  return 0;
}