A17497. 传话对象
填空题
困难
知识点
题目描述
传话对象
题目描述
在一个公司里，有 n 名员工，编号 1 到 n。每名员工都有一个“传话对象”，即第 ii 名员工只会把消息告诉第 ti 名员工（允许告诉自己）。现在，从每名员工出发，依次沿着传话对象传递消息，可以证明经过有限步后，消息一定会回到一个已经传过的员工。
请你分别计算：从第 i 名员工开始，需要传递多少步后，才会第一次遇到一个已经传过消息的员工。
输入格式
第一行，一个整数 n。
第二行，n 个整数 t1,t2,…,tn，表示第 i 名员工的传话对象。
输出格式
输出 n 行，第 i 行一个整数，表示从第 i 名员工出发的答案。
输入样例
4
2 1 1 4输出样例
2
2
3
1说明提示
1≤n≤5×105
参考答案
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int MAXN = 5e5 + 10;
int t[MAXN];
int vis[MAXN]; // 0未访问 1访问中 2已处理
int ans[MAXN];
vector<int> path;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> t[i];
}
for (int i = 1; i <= n; i++) {
if (vis[i] != 0) continue;
path.clear();
int cur = i;
while (true) {
if (vis[cur] == 1) {
// 找到环起点：cur在path中的位置
int pos = 0;
while (path[pos] != cur) pos++;
// 环部分 [pos, end]
int ring_len = path.size() - pos;
for (int j = pos; j < path.size(); j++) {
ans[path[j]] = ring_len;
vis[path[j]] = 2;
}
// 树链部分 [0, pos-1] 倒推
for (int j = pos - 1; j >= 0; j--) {
ans[path[j]] = ans[t[path[j]]] + 1;
vis[path[j]] = 2;
}
break;
}
if (vis[cur] == 2) {
// 当前路径全部是树链，用已处理点倒推
for (int j = path.size() - 1; j >= 0; j--) {
ans[path[j]] = ans[t[path[j]]] + 1;
vis[path[j]] = 2;
}
break;
}
// 未访问，加入路径标记为访问中
vis[cur] = 1;
path.push_back(cur);
cur = t[cur];
}
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << '\n';
}
return 0;
}
上一题
下一题