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