P10693 题解

· · 题解

P10693 题解

温馨提醒：本题解约一千字，请耐心看完。

题目思路

首先所有题解都会告诉你要连一条从 i \rightarrow a_i 的边，但为什么要这样连呢？下面我会手搓几组小数据，分析这种方法的思路。

先看样例，这对应着一种情况：如果所有的 a_i 都不相同，那么结果一定为 n。我试图对这个结论推广为：答案为所有 a_i 中不同的个数。显然这个结论对于样例成立，但提交记录告诉我这个结论是错误的。

于是我搓了另一组数据：

5
2 3 4 5 5

我将刚刚的结论带入，发现这与真正的答案并不相同。用刚刚的结论得到的结果为 4，但当你尝试让 1 \sim 4 号都坐在心仪的位置上时，5 号就没有地方坐了；如果让 1 \sim 3 号和 5 号坐在心仪的位置上时，由于 a_3 = 4，所以 4 号就没有位置坐了。

这时我们就可以引出开头说的连边方式的原因了：我们假设让 i 号坐在心仪的位置上时，a_i 这个位置自然不能坐其他的人，这时第 a_i (a_i \le n) 个人只能接着坐到自己的心仪位置，自然就是 a_i 向自己的心仪位置连边（当然保证 a_i \le n）。

连边方式有了，答案怎么确定呢？这时研究一下我给出的数据就会发现：当 i = 5 时，a_i = 5，此时 i \rightarrow a_i 的连边形成了一个环。也就是说，如果有环，那么环中的人都可以坐到自己的心仪位置上，而且不会影响到环外的人坐座位。

然而我们模拟样例连边就会发现，图中形成了两个部分：一个是 1 \rightarrow 2 \rightarrow 6 的链；另一个是 3 \rightarrow 4 \rightarrow 5 \rightarrow 3 的环。这时候出现了新的可能的连边情况：链，当然更准确的说是有向树（这种数据在本文章中并没有列出，但仍然可以构造）。对于这种情况，我们使用 DFS 求出最大深度，取这一条路径上的所有点，这些人可以坐到他们的心仪位置上。

但是还有最后的问题：上一段中的最大路径应该怎么求？这里先给出结论：本题的有向树中只会有一个点的编号 > n，从这个点出发反向寻找即为最长路径。那么为什么只会有一个点编号 > n 呢？考虑反证法：设没有点的编号 > n，即所有点编号都 \le n。此时一定有一个点没有向其他点连过边，而这个点的编号又 \le n，那么设这个点为 i,一定可以连一条 i \rightarrow a_i 的边，如果此时 a_i \le n，则可以继续通过刚刚的方式连边。最后只会有两种可能：第一，所有点的编号都 \le n，而此时没有边可连，这形成了环；第二，找到了一个 a_i > n，连边结束。这两种情况都与原假设不符，故证明成功。

所以，我们需要从 > n 的编号开始反向找最长路径（所以需要反向连边）；还需要判断图中所有的环（可以用拓扑排序，没有访问过的点即为环上的点），并将两部分答案相加，输出即可。

题目代码

注：代码略去缺省源部分，若希望看到缺省源，点击这里。

int a[200005];
int ans;
int maxdep;
int n;
vector < int > v[200005]; // 反向图
vector < int > tppx[200005]; // 正向图，拓扑排序用
int in[200005];
bool flag[200005]; // 判一下有没有被 DFS 求路径，防止拓扑排序之后答案重复
void dfs(int now , int dep)
{
    if(now <= n)
    {
        flag[now] = 1; // 防止这个点被加入拓扑排序
        maxdep = max(maxdep , dep);
    }
    for(int i : v[now])
    {
        dfs(i , dep + 1);
    }
}
signed main()
{
    read(n);
    readarray(a , 1 , n);
    for(int i = 1 ; i <= n ; i++)
    {
        v[a[i]].push_back(i);
        tppx[i].push_back(a[i]);
        in[a[i]]++;
    }
    for(int i = n + 1 ; i <= n * 2 ; i++)
    {
        maxdep = 0;
        dfs(i , 0);
        // 路径上的第一个点 ~ 倒数第二个点都会整体向后平移一位
        // 所以实际上路径上如果有 x 个点，这一部分答案只有 x - 1
        // 所以初始深度设为 0 可以计算出正确答案
        // 设成 1 最后 maxdep - 1 其实也行
        ans += maxdep;
    }
    queue < int > q;
    for(int i = 1 ; i <= n ; i++)
    {
        if(!in[i] && !flag[i])
        {
            q.push(i);
        }
    }
    while(q.size())
    {
        int now = q.front();
        q.pop();
        flag[now] = 1;
        for(int i : tppx[now])
        {
            if(--in[i] == 0)
            {
                q.push(i);
            }
        }
    }
    for(int i = 1 ; i <= n ; i++)
    {
        ans += !flag[i];
        // 没进入拓扑排序就是环上的点
        // 因为一个环不可能单独拆出一个点入度为 0
    }
    printnl(ans);
    return 0;
}