蓝桥杯2018年第九届真题-小朋友崇拜圈(有向图强连通分量)

#include<bits/stdc++.h>
using namespace std;
#define maxx 310000
int a,n,anss;
int ans[maxx];
vector<int> G[maxx];
int pre[maxx],lowlink[maxx],sccno[maxx],dfs_clock,scc_cnt;
stack<int> S;
void dfs(int u)
{
    pre[u]=lowlink[u]=++dfs_clock;
    S.push(u);
    for(int i=0;i<G[u].size();++i)
    {
        int v=G[u][i];
        if(!pre[v])
        {
            dfs(v);
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }
        else if(!sccno[v])
        {
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u])
    {
        scc_cnt++;
        for(;;)
        {
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u) break;
        }
    }
}
int main()
{
  cin>>n;
  for(int i=1;i<=n;++i)
  {
    cin>>a;
    G[a].push_back(i);
     
  }
  for(int i=1;i<=n;++i)
  if(pre[i]==0) dfs(i);
  for(int i=1;i<=n;++i) ++ans[sccno[i]];
  for(int i=1;i<=n;++i) anss=max(anss,ans[i]);
  cout<<anss;
    
   
}