Main » 2013 October 23 » [NOIP2012模拟赛No.14]Trick or Treat on Farm
3:16 PM [NOIP2012模拟赛No.14]Trick or Treat on Farm |
终于想出来怎么处理环了#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 300010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int nxt[N],len[N],vis[N],n,p,cnt; void dfs(int x,int T) { if (vis[x]==T) { p=x,cnt=1; while (nxt[p]!=x) p=nxt[p],cnt++; p=x;len[p]=cnt; while (nxt[p]!=x) { p=nxt[p]; len[p]=cnt; } return; } if (vis[x]!=0) return; vis[x]=T; dfs(nxt[x],T); if (!len[x]) len[x]=len[nxt[x]]+1; } int main() { scanf("%d",&n);int i; FOR(i,1,n) scanf("%d",&nxt[i]); memset(vis,0,sizeof(vis)); memset(len,0,sizeof(len)); int T=0; FOR(i,1,n) if (!vis[i]) dfs(i,++T); FOR(i,1,n) printf("%d\n",len[i]); } |
|
|
| Total comments: 0 | |