Luogu P2921 – 图的遍历

PROBLEM

https://www.luogu.org/problemnew/show/P2921

ANALYSIS

寻找从每个点出发到访问到已访问节点(将环封闭)用的时间。

起初自己的想到解法应该和 [lip id=893] 差不多,然而在原先题目的思路去思考这个问题有点受限。

 

一种正确的做法:

从所有点开始,尝试对节点染色。

对于遍历的终止条件,有以下两种情况:

  1. 访问到了已经被自己染色的节点;
  2. 访问到了已经被别人染色的节点。

对于 情况1,我们可以直接退出,并且输出当前的时间戳(cnt )。

对于 情况2,又有两种情况:

  1. 访问到了环中节点;
  2. 访问到了环的分支节点(在前往环的路上)。

对于 情况a,输出为 时间戳 + 环的长度

对于 情况b,输出为 时间戳 + 前往环的路的长度 + 环的长度

环的长度,可以在 情况1 退出前, 保存 最后一次搜索的时间戳 – 最后一个访问到的节点的时间戳 作为环的长度。

前往环的路的长度,可以在 情况1 退出前,可以转换为 进入环的时间戳 ,在退出时保存 最后一个访问到的节点的时间戳 作为前往环的路的长度 。

至此,容易想到在 情况2 退出前,保存两者的方法。

SOLUTION

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100010;

/**
 * n 个数
 * nxt 下一个位置
 * color 染色 (可以理解为anc?)
 * sucdfn 入环时间戳
 * dfn 递归时间戳
 * minc 环长度
 */
int n, nxt[N], color[N], sucdfn[N], dfn[N], minc[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> nxt[i];
    }
    for (int cow = 1; cow <= n; ++cow) {
        for (int i = cow, cnt = 0; ; i = nxt[i], ++cnt) {
            if (!color[i]) {
                // 如果从未被访问过
                color[i] = cow;
                dfn[i] = cnt;
            } else if (color[i] == cow) {
                // 如果回到了自己经过的点,将环关闭
                minc[cow] = cnt - dfn[i];
                sucdfn[cow] = dfn[i];
                cout << cnt << endl;
                break;
            } else {
                // 如果在某一点进入了已访问过的节点
                // 复制环的长度
                minc[cow] = minc[color[i]];
                // 环长度与anc环长度一致
                sucdfn[cow] = cnt + max(sucdfn[color[i]] - dfn[i], 0);
                // **如果实际上没有进入环,而是进入了环外分支**
                cout << sucdfn[cow] + minc[cow] << endl;
                break;
            }
        }
    }
    return 0;
}

 

REFERENCE

  1. https://www.luogu.org/blog/planetarian/solution-p2921

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注