其实就是一张图 可知每个点出度为一
由于有环 所以把整个图缩点后会好做得多
在缩点后 每个强联通分量的出度至多为一。
然后我们dfs 直接搜很危险 考虑记忆化 设ans[i]代表第i个强连通分量的答案就好了
详见代码
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define N 100005 using namespace std; struct node { int to,next; }edge[2*N]; int n,nxt[N],first[N],tot,dfn[N],low[N],num,sign,belong[N],out[N],size[N],ans[N]; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } stack <int> sta; bool insta[N]; void dfs1(int now) { sta.push(now); dfn[now]=low[now]=++sign; insta[now]=true; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(!dfn[vis]) { dfs1(vis); low[now]=min(low[now],low[vis]); } else if(insta[vis]) low[now]=min(low[now],dfn[vis]); } if(low[now]==dfn[now]) { int temp; num++; do { size[num]++; temp=sta.top(); insta[temp]=false; belong[temp]=num; sta.pop(); }while(temp!=now); } } int dfs2(int now) { if(ans[now]||!now) return ans[now]; return ans[now]=dfs2(out[now])+size[now]; } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>nxt[i]; addedge(i,nxt[i]); } for(int i=1;i<=n;i++) if(!dfn[i]) dfs1(i); for(int i=1;i<=n;i++) { if(belong[i]!=belong[nxt[i]]) out[belong[i]]=belong[nxt[i]]; //每个点出度为1 } for(int i=1;i<=n;i++) { dfs2(belong[i]); } for(int i=1;i<=n;i++) cout<<ans[belong[i]]<<'\n'; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9807292.html
相关资源：各显卡算力对照表！