P2921 [USACO08DEC]在農場萬圣節Trick or Treat on the Farm

對于一個牛，它存在兩種狀態：1.處于聯通分量 2.不處于聯通分量。對于處于聯通分量的牛，求出聯通分量的大小；對于不處于聯通分量的牛，求出其距離聯通分量的路程+聯通分量大小。

不同的聯通分量，染上不同的顏色，可以計算各個聯通分量的大小。

#include<bits/stdc++.h>
using namespace std;int vis[100005];
int low[100005];
int Loop[100005],color[100005],dfn[100005],head[100005],ans[100005],st[100005], Next[100005];
int pos;
int k=1;
int col;
int top;struct node
{int v,next;
}edge[100005];void Add(int u,int v)
{edge[k].v = v;edge[k].next = head[u];head[u] = k++;
}void Find(int root,int x,int step)
{if(ans[x]!=0){ans[root] = ans[x]+step;return;}elseFind(root,Next[x],step+1);
}void Tarjan(int u)
{dfn[u] = low[u] = ++pos;st[++top] = u;vis[u] = 1;for(int i=head[u];i!=-1;i=edge[i].next){int v = edge[i].v;if(!dfn[v]){Tarjan(v);low[u] = min(low[u],low[v]);}else if(vis[v]){low[u] = min(low[u],dfn[v]);}}if(dfn[u] == low[u]){col++;int x;do{x = st[top--];vis[x] = 0;color[x] = col;}while(x!=u);}
}int main()
{memset(head,-1,sizeof(head));int n,v;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&v);Next[i] = v;Add(i,v);if(v==i)ans[i] = 1;}for(int i=1;i<=n;i++){if(!dfn[i]){Tarjan(i);}}for(int i=1;i<=n;i++){Loop[color[i]]++;}for(int i=1;i<=n;i++){if(Loop[color[i]]!=1)ans[i] = Loop[color[i]];}for(int i=1;i<=n;i++){if(ans[i]==0)Find(i,Next[i],1);}for(int i=1;i<=n;i++){printf("%d\n",ans[i]);}return 0;
}

?