1 条题解
-
1
发现每一个点都只有一个出边,所以形成了一个基环树森林。
记录每一个点下一条点和上一条点,大分讨即可。
注意利用以前的信息,否则时间复杂度会退化到 。
注意特判点不在环上的情况。
时间复杂度 (应该是)
// This guy is too lazy so that he/she write nothing. #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int nxt[N], deg[N], dis[N], step[N]; vector<int> pre[N]; bool vis[N], vis2[N], vis3[N]; signed main() { int n; cin >> n; for (int i = 1; i <= n; i++) { int x; cin >> x; nxt[i] = x; pre[x].push_back(i); deg[i]++, deg[x]++; } memset(dis, 0x3f, sizeof dis); for (int i = 1; i <= n; i++) if (!vis[i]) { int j = i, cnt = 0, laj; vector<int> tlist; while (!vis[j]) { vis[j] = true; vis2[j] = true; tlist.push_back(j); step[j] = cnt++; laj = j; j = nxt[j]; } if (vis2[j]) // 在环上 { for (auto &j : tlist) vis2[j] = false; int k = cnt - step[j]; queue<int> q; tlist.clear(); int tk = j; do { q.push(j); tlist.push_back(j); dis[j] = k; j = nxt[j]; vis2[j] = true; } while (tk != j); while (q.size()) { int f = q.front(); q.pop(); vis2[f] = false; for (auto &j : pre[f]) if (dis[j] > dis[f] + 1) { dis[j] = dis[f] + 1; if (!vis2[j]) { vis2[j] = true; q.push(j); tlist.push_back(j); } } } } else // 不在环上 { queue<int> q; q.push(j); for (auto &j : tlist) vis2[j] = false; vis2[j] = true; tlist.clear(); tlist.push_back(j); while (q.size()) { int f = q.front(); q.pop(); vis2[f] = false; for (auto &j : pre[f]) if (dis[j] > dis[f] + 1) { dis[j] = dis[f] + 1; if (!vis2[j]) { vis2[j] = true; q.push(j); tlist.push_back(j); } } } } for (auto &j : tlist) vis2[j] = false; } for (int i = 1; i <= n; i++) cout << dis[i] << '\n'; return 0; }
- 1
信息
- ID
- 1589
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 5
- 已通过
- 3
- 上传者