Description
每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N(1≤N≤100000)个牛棚里转悠，来采集糖果．她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果． 农场不大，所以约翰要想尽法子让奶牛们得到快乐．他给每一个牛棚设置了一个“后继牛棚”．牛棚i的后继牛棚是Xi．他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果．事实上这是一种有点欺骗意味的手段，来节约他的糖果． 第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果．
Input
第1行输入N，之后一行一个整数表示牛棚i的后继牛棚Xi，共N行．
Output
共N行，一行一个整数表示一只奶牛可以采集的糖果数量．
Sample Input
4 //有四个点
1 //1有一条边指向1
3 //2有一条边指向3
2 //3有一条边指向2
3
1 //1有一条边指向1
3 //2有一条边指向3
2 //3有一条边指向2
3
INPUT DETAILS:
Four stalls.
* Stall 1 directs the cow back to stall 1.
* Stall 2 directs the cow to stall 3
* Stall 3 directs the cow to stall 2
* Stall 4 directs the cow to stall 3
Sample Output
1
2
2
3
2
2
3
HINT
Cow 1: Start at 1, next is 1. Total stalls visited: 1. Cow 2: Start at 2, next is 3, next is 2. Total stalls visited: 2. Cow 3: Start at 3, next is 2, next is 3. Total stalls visited: 2. Cow 4: Start at 4, next is 3, next is 2, next is 3. Total stalls visited: 3.
Source
Gold
Solution
强联通缩点。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<iostream> #include<cstdio> using namespace std; const int N=100100; int n,tot,now,top,cnt,x[N],Next[N<<1],head[N],tree[N<<1],dfn[N],low[N],stack[N];; int belong[N],size[N],ans[N]; bool ins[N],visit[N]; void add(int x,int y) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; } void Tarjan(int u) { dfn[u]=low[u]=++now; stack[++top]=u;ins[u]=true; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); }else if (ins[v]) low[u]=min(low[u],dfn[v]); } if (dfn[u]==low[u]) { int i; cnt++; do { i=stack[top--]; ins[i]=false; belong[i]=cnt; size[cnt]++; }while (i!=u); } } void dfs(int u) { ans[u]=size[u]; if (size[u]!=1) return; for (int i=head[u];i;i=Next[i]) { if (!ans[tree[i]]) dfs(tree[i]); ans[u]+=ans[tree[i]]; } } int main() { scanf("%d",&n); tot=now=top=cnt=0; for (int i=1;i<=n;i++) { scanf("%d",&x[i]); add(i,x[i]); } for (int i=1;i<=n;i++) ins[i]=false; for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i); tot=0; for (int i=1;i<=n;i++) head[i]=0; for (int i=1;i<=n;i++) if (belong[i]!=belong[x[i]]) add(belong[i],belong[x[i]]); for (int i=1;i<=cnt;i++) if (!ans[i]) dfs(i); for (int i=1;i<=n;i++) printf("%d\n",ans[belong[i]]); return 0; } |
