先做拓扑排序，再bfs处理
#include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include< string> #include<algorithm> #include<map> #include<stack> #include<queue> #include<vector> #include<cmath> #include<utility> using namespace std; typedef long long LL; const int N = 210008, INF = 0x3F3F3F3F; #define MS(a, num) memset(a, num, sizeof(a)) #define PB(A) push_back(A) #define FOR(i, n) for(int i = 0; i < n; i++) bool vis[N]; struct Node{ int to,next; }edge[N]; int head[N], tot, n,m,indeg[N]; int fa[N]; void init(){ memset(head, - 1, sizeof(head)); memset(indeg, 0, sizeof(indeg)); tot = 0; } void add( int u, int to){ indeg[to]++; edge[tot].to=to; edge[tot].next=head[u]; head[u]=tot++; } void Topsort(){ stack < int> st; for( int i = 1;i<=n; i++) { if(indeg[i]== 0) { st.push(i); } } while(!st.empty()){ int cur = st.top(); st.pop(); vis[cur] = 1; for( int i = head[cur]; i != - 1; i = edge[i].next){ int to= edge[i].to; indeg[to]--; if(!indeg[to]){ st.push(to); } } } } void bfs( int u){ queue< int> q; q.push(u); vis[u] = 1; while(!q.empty()){ int u = q.front(); q.pop(); for( int i= head[u]; i != - 1; i = edge[i].next){ int to = edge[i].to; if(!vis[to]){ vis[to] = 1; q.push(to); } } } } int main(){ cin>>n; MS(vis, 0); init(); for( int i = 1;i <= n ;i++){ int u; scanf( " %d ", &u); fa[i] = u; add(i, u); } Topsort(); int v = 0; for( int i = 1;i <= n; i++){ if(fa[i] == i){ vis[i] = 1; v = i; break; } } if(v == 0){ for( int i = 1;i <= n; i++){ if(!vis[i]){ fa[i] = i; v = i; break; } } } int cnt = 0; for( int i = 1; i <= n; i++){ if(!vis[i]){ fa[i] = v; cnt++; bfs(i); } } cout<<cnt<< ' \n '; cout<<fa[ 1]; for( int i = 2;i <= n;i++){ printf( " %d ", fa[i]); } return 0;
}