本人对tarjan理解不够深刻，此贴结
by _Hugoi_ @ 2023-10-23 17:58:25
```cpp
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <math.h>
#include <functional>
#define endl '\n'
#define ull unsigned long long
#define ll long long
#define pii pair<ll ,ll>
#define cy cout<<"YES"<<'\n'
#define cn cout<<"NO"<<'\n'
#define forn(i,begin,end,add) for(ll (i)=(begin);(i)<=(end);(i)+=(add)) //begin是i的起始，end是i的终止，add是每次加的大小
#define rforn(i,begin,end,sub) for(ll (i)=(end);(i)>=(begin);(i)-=(sub)) //r是倒序遍历
#define vv vector
#define inf32 INT32_MAX/2
#define inf64 INT64_MAX/4
#define LD long double
#define PI acos(-1)
#define debug(a,b) cout<<a<<b
#define eps 1e-12
const int N = 2e5 + 100;
const int mod = 998244353;
ll T;
vv<vv<int>>e(N);
vv<ll>instk(N);
vv<ll>dfn(N);
vv<ll>low(N);
vv<ll>siz(N);
vv<ll>scc(N);
stack<ll>st;
int cnt = 0, tot = 0;
vv<ll>all(N);
void tarjan(int x) {
dfn[x] = low[x] = ++tot;
st.push(x), instk[x] = true;
for (int y : e[x]) {
//if(y==x) 出现自环
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (instk[y]) {//y还没往下走，所以用dfn更新
low[x] = min(low[x], dfn[y]);//其实用low也行，因为dfn=low=++tot
}
//如果一个点既不在栈中，又已经走过了，不需要再走了，因为横跨边无法更新任何东西
}
//离开x时，记录scc
if (dfn[x] == low[x]) {
int y; ++cnt;
do {
y = st.top(); st.pop();
instk[y] = false;
scc[y] = cnt;
++siz[cnt];//强连通分量的大小
} while (y != x);
}
}
vv<vv<int>>re(N);
void dfs(int u, int sz) {
all[u] = sz;
for (auto a : re[u]) {
if (scc[a] != scc[u])
dfs(a, sz + 1);
}
}
void solve() {
int n; cin >> n;
forn(i, 1, n, 1) {
int a; cin >> a;
e[i].push_back(a);
re[a].push_back(i);
if (a == i)
all[i] = 1;
}
forn(i, 1, n, 1)
if (!dfn[i])
tarjan(i);
forn(i, 1, n, 1) {
if (siz[scc[i]] > 1)
dfs(i, siz[scc[i]]);
}
forn(i, 1, n, 1)
if (siz[scc[i]] == 1)
cout << all[i] << endl;
else
cout << siz[scc[i]] << endl;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
T = 1;
//cin >> T;
while (T--)
solve();
return 0;
}
```
@[_Hugoi_](/user/525402)
by Exile_Code @ 2024-04-10 19:25:21
@[_Hugoi_](/user/525402) 佬可以帮忙调一下嘛
by Exile_Code @ 2024-04-10 19:25:42