洛谷P9150 邮箱题题解

题意：

有一张 \(n\) 个点和 \(m\) 条边构成的有向图。每个点内都有一把另一个点的钥匙，\(i\) 号点内有 \(k_i\) 号点的钥匙。你能进入一个点当且仅当你有该点的钥匙。保证 \(k_i\) 构成排列。

只要进入了一个点，就获得了这个点内有的钥匙。一旦获得钥匙就不会被消耗。

现在你拿到了 \(i\) 号点的钥匙并到了 \(i\) 号点。你需要对每个 \(i\) 求出：

有多少点能被你到达。

有多少点能被你到达并返回起点 \(i\)。

请注意：给出的边均是有向边！

输入格式：

本题有多组数据。

第一行，一个正整数 \(T\)，表示数据的组数。对于每组数据：

第一行，两个整数 \(n,m\)，表示图的点数和边数。

第二行，\(n\) 个整数 \(k_1, k_2, \ldots, k_n\)，表示 \(i\) 号点内有 \(k_i\) 号点的钥匙。保证 \(k_i\) 构成排列。

接下来 \(m\) 行，每行两个整数 \(x, y\)，表示图上的一条从 \(x\) 指向 \(y\) 的有向边。保证不含重边或自环。

输出格式：

对于每组数据，输出 \(n\) 行，每行两个整数，第 \(i\) 行的整数分别表示从 \(i\) 号点出发，能到达的点数和能到达并返回起点的点数。

数据范围：

保证图中不含重边或自环。

满足 \(n \ge 3\)，\(m\ge 0\)，\(\sum n\le 1.5\times{10}^6\)，\(\sum m\le 3\times{10}^6\)，\(1 \le T\le 2\times{10}^4\)，\(1 \le x, y \le n\) 。

由于每个点只有一把钥匙，且钥匙的数量不会超过进入的点的数量 \(+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 \not\in a\) 。这等价于 \(k_j \ne i\) ，因为 \(k\) 形成排列，而除了 \(i\) 都不可能有更多到达的边了。
考虑路径上最大的 \(p\) 的使得 \(a_p\) 与 \(k_j\) 存在边 \(a_p \to k_j\) ，\(a_p\) 应当存在且 \(j\) 可以回到 \(a_p\) 。

关于条件二的判断，因为 \(a_i\) 可以到达 \(a_{i+1}\) ，所以只需在每次新进入点 \(j\) 时，考虑其所有的返祖边 \(j \to a_q\)

则 \(a_q\) 到 \(j\) 的路径上所有点强连通。枚举 \(k_j\) 的入边 \(u \to k_j\) ，若 \(u \in a\) 且 \(u\) 和 \(j\) 强连通，则 \(k_j\) 可达。

用并查集维护强连通分量的合并过程，我们可以得到一个 \(\mathcal{O}(n^2\alpha(n))\) 的暴力。

至此我们还没有很好的利用 \(k\) 形成排列这一性质，因此我们把 \(k\) 上所有的环拎出来单独探究其特点。

首先断环成链，也就是把环再复制一份拼到后面，记为序列 \(c\) 。

则每个点 \(c_j\) 的前一个 \(c_{j-1}\) 在链上的答案就是它在环上的答案。

因为从后继（指 \(k\) 值）的点出发，不会到达之前的点，所以我们从后往前加入计算每个点的答案

显然如果 \(x\) 可达 \(y\) ，\(y\) 可达 \(z\) ，则 \(x\) 可达 \(z\) ，也就是具有传递性。

考虑设已知 \(c_{i+1}\) 到 \(c_{L}\) 的答案，如何计算 \(c_i\) 的答案。那么这整个过程相当于不断尝试合并第一条链和第二条链

设第一条链的末尾为 \(c_p\) ，第二条链的开头为 \(c_{p+1}\) ，考虑 \(c_{p+1}\) 的最大 \(u\) 满足 \(i \le u \le p\) 。

若 \(c_u\) 存在且和 \(c_p\) 强连通，则可以合并，反之则无法合并。

用两个并查集分别维护这个表示可达性的链和强连通分量，并预处理每个点的那个最大 \(u\) 。

那么怎么合并呢？如果两条链可以合并，那么第一条链的开头，即当前 \(c_i\) 一定产生了贡献

否则在加入 \(c_i\) 之前这两条链就已经可以合并了；而如果 \(c_i\) 要产生贡献，

它一定将第一条链的末尾 \(c_p\) 所在强连通分量扩大了，这说明 \(c_i\) 与 \(c_p\) 在同一强连通分量。

这样对于每条链，只需维护 \(c\) 上编号最大的有还未统计过的返祖边的节点。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e6 + 15))

char vis[N];
int n,m,c,k[N],a1[N],a2[N],cyc[N],in[N],val[N],pre[N];
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 u,int v) { fa[find(v)] = find(u); }
}c1, c2;
void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) e[i].clear();
    memset(vis, 0, sizeof(char) * (n + 5));
    for(int i = 1; i <= n; i++) cin >> k[i];
    for(int i = 1, u,v; i <= m; i++) {
        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--)
        {
            c1.fa[j] = c2.fa[j] = j;
            val[j] = pre[j] = 0;
            int id = cyc[j > c ? j - c : j];
            for(int t : e[id]) {
                if(!in[t]) continue; else t = in[t];
                if(t + c < j) t += c; if(t > j) t -= c;
                up(pre[j], t); 
                if(t < j) t += c; if(t <= c * 2) up(val[c2.find(t)], c1.find(t));
            }
            while(true)
            {
                while(true)
                {
                    int x = c1.find(j), y = c2.find(j);
                    if(x < val[y]) c1.merge(x + 1, x); else break;
                }
                int x = c1.find(j), y = c2.find(j);
                val[y] = 0;
                if(y == c * 2 || x != y || pre[y + 1] < j) break;
                c2.merge(y + 1, y);
            }
            a1[id] = min(c, c2.find(j) - j + 1);
            a2[id] = min(c, c1.find(j) - j + 1);
        }
        for(int j = 1; j <= c; j++){ in[cyc[j]] = 0; vis[cyc[j]] = 1; }
        c = 0;
    }
    for(int i = 1; i <= n; i++) cout << a1[i] << ' ' << a2[i] << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}