自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:45:49，当前版本为作者最后更新于2023-03-18 00:07:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9150 邮箱题

好久没见到这么小清新的图论题了。上次见到还是在 上次。

首先，因为进入一个点时必然有该点的钥匙，而钥匙的数量不会超过进入的点的数量 $+1$，所以在任意时刻，接下来新进入的点是固定的，且该点的钥匙在上一个新进入的点内。因此，如果从 $i$ 号点出发，只需在已经进入的点的基础上，依次考虑 $k_i, k_{k_i}, \cdots$ 是否可达。

考虑当前点 $j$ 以及从 $i$ 不断跳 $k_i$ 到 $j$ 的序列 $a = \{i, k_i, k_{k_i},\cdots, j\}$。我们探究 $k_j$ 可达的充要条件：

• $k_j\notin a$。这等价于 $k_j \neq i$，因为 $k$ 形成排列。
• 考虑路径上最靠近 $j$ 的 $k_j$ 的入边，即最大的 $p$ 使得 $a_p\to k_j$，$a_p$ 存在且 $j$ 可以回到 $a_p$。

如何判定条件二呢？因为 $a_i$ 可达 $a_{i + 1}$，所以只需在每次往序列中加入 $a_p = j$，即新进入点 $j$ 时，考虑其所有 “返祖边” $a_p\to a_q$（$p > q$），则 $a_q\sim a_p$ 之间所有点强连通。枚举 $k_j$ 的入边 $u\to k_j$，若 $u\in a$ 且 $u$ 和 $j$ 强连通，则 $k_j$ 可达。

用并查集维护强连通分量的合并过程，我们得到了 $\mathcal{O}(n ^ 2\alpha)$ 的做法。

因为 $k$ 形成排列，所以我们将 $k$ 上的所有环拎出来单独考虑。

首先断环成链，将环复制两份得到序列 $c$。我们认为一个点的 $k$ 值为其后继，则每个点的前一份复制品在链上的答案就是它在环上的答案。因为从后面的点出发，不会到达前面的点，所以我们从后往前加入计算每个点的答案。

若从 $x$ 出发可达 $y$，从 $y$ 出发可达 $z$，则从 $x$ 出发可达 $z$，因为从 $x$ 出发到达 $y$ 之后，一定拥有 $y$ 号点的钥匙。因此，可达性具有传递性，可以用若干条链描述。

设 $c_{i + 1}\sim c_{L}$ 的答案已知，计算 $c_i$ 的答案，则整个过程相当于不断尝试合并第一条链和第二条链。设第一条链的末尾为 $c_p$，第二条链的开头为 $c_{p + 1}$，根据朴素做法中的判定条件，考虑 $c_{p + 1}$ 的最靠近 $c_p$ 且落在 $c_i\sim c_p$ 上的入边 $c_u\to c_{p + 1}$（$i\leq u\leq p$ 且 $u$ 最大），若 $c_u$ 存在且和 $c_p$ 强连通，则可以合并，否则无法合并。

用两个并查集分别维护可达链和强连通分量，预处理每个点在链上最靠近它且在它前方的入点的位置即可。

问题来了，合并两条可达链的时候，强连通分量该怎么合并？虽然产生贡献的返祖边数量总数只有 $\mathcal{O}(m)$，但我们不能直接枚举第二条链上的所有返祖边，因为这样无法跳过不产生贡献的返祖边。一个解决方案是，对每个可达链，维护所有终点编号不小于 $i$ 且 还没考虑过 的返祖边。合并两条链时，统计第二条链维护的所有返祖边的影响，并将它们全部删除。这样，新链的返祖边集合就等于第一条链的返祖边集合，不需要启发式合并。

至此已经得到 $\mathcal{O}(n\alpha)$ 的做法，但是不优美。

我们注意到，如果两条链可以合并，那么第一条链的开头，即当前的 $c_i$ 一定产生了贡献，否则在加入 $c_i$ 之前这两条链就已经可以合并了。而如果 $c_i$ 要产生贡献，一定将第一条链的末尾 $c_p$ 所在的强连通分量扩大了，这说明 $c_i$ 和 $c_p$ 在同一强连通分量，即 第一条链整体是一个强连通分量。这样，对于每条链，只需维护编号最大的有还未统计过的返祖边的节点，因为这些返祖边具体指向哪些点是不重要的，反正它们在同一个强连通分量，而每个起始点都相当于将 $c_i$ 到该起始点的强连通分量全部合并，所以我们只关心编号最大的起始点。

此外，有了该性质，在判定是否可以合并两条链时，也可以维护每个点 $c_{p + 1}$ 是否被之前 $c_i\sim c_p$ 的某个点指向，代替计算每个点的最近前驱的位置，但这样就要存正向边了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

bool Mbe;
constexpr int N = 3e6 + 5;
void cmax(int &x, int y) {x = x > y ? x : y;}

int n, m, k[N], a1[N], a2[N];
bool vis[N]; // vis 表示是否被访问过
int c, cyc[N], in[N], val[N], pre[N]; // in 表示结点在环上的编号，val 表示结构编号最大的有返祖边的分量，pre 表示结点的最近前驱入边位置
vector<int> e[N];
struct dsu {
  int fa[N];
  int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
  void merge(int a, int b) {fa[find(b)] = find(a);}
} cy, ch; // 维护环（强连通分量）和链的并查集

void solve() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++) e[i].clear();
  memset(vis, 0, n + 2);

  for(int i = 1; i <= n; i++) cin >> k[i];
  for(int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[v].push_back(u);
  }

  for(int i = 1; i <= n; i++) {
    if(vis[i]) continue;
    int p = i;
    while(!in[p]) cyc[++c] = p, in[p] = c, p = k[p];
    for(int j = c * 2; j; j--) {
      cy.fa[j] = ch.fa[j] = j, val[j] = pre[j] = 0;
      int id = cyc[j > c ? j - c : j];
      for(int it : e[id]) {
        if(!in[it]) continue;
        it = in[it];
        if(it + c < j) it += c;
        if(it > j) it -= c;
        pre[j] = max(pre[j], it);
        if(it < j) it += c;
        if(it <= c * 2) cmax(val[ch.find(it)], cy.find(it));
      }
      while(1) {
        while(1) {
          int cyid = cy.find(j), chid = ch.find(j);
          if(cyid < val[chid]) cy.merge(cyid + 1, cyid);
          else break;
        }
        int cyid = cy.find(j), chid = ch.find(j);
        val[chid] = 0;
        if(chid == c * 2 || cyid != chid || pre[chid + 1] < j) break;
        ch.merge(chid + 1, chid);
      }
      a1[id] = min(c, ch.find(j) - j + 1);
      a2[id] = min(c, cy.find(j) - j + 1);
    }
    for(int i = 1; i <= c; i++) in[cyc[i]] = 0, vis[cyc[i]] = 1;
    c = 0;
  }
  for(int i = 1; i <= n; i++) cout << a1[i] << " " << a2[i] << "\n";
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin); 
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T;
  cin >> T;
  while(T--) solve();
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}