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

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.