P2921 USACO08DEC 在农场万圣节Trick or Treat on the Farm

本文主要是介绍P2921 USACO08DEC 在农场万圣节Trick or Treat on the Farm，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

万圣节又要到了（大雾），可恶机智的农场主又要给欺骗奶牛们发糖果了。

题目描述

Every year in Wisconsin the cows celebrate the USA autumn holiday of Halloween by dressing up in costumes and collecting candy that Farmer John leaves in the N (1 <= N <= 100,000) stalls conveniently numbered 1..N.

Because the barn is not so large, FJ makes sure the cows extend their fun by specifying a traversal route the cows must follow. To implement this scheme for traveling back and forth through the barn, FJ has posted a 'next stall number' next_i (1 <= next_i <= N) on stall i that tells the cows which stall to visit next; the cows thus might travel the length of the barn many times in order to collect their candy.

FJ mandates that cow i should start collecting candy at stall i. A cow stops her candy collection if she arrives back at any stall she has already visited.

Calculate the number of unique stalls each cow visits before being forced to stop her candy collection.

POINTS: 100

输入输出格式

input

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer: next_i

output

* Lines 1..N: Line i contains a single integer that is the total number of unique stalls visited by cow i before she returns to a stall she has previously visited.

输入输出样例

输入样例#1：

输出样例#1：

说明

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

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.

你以为我看的懂英文？？？（刚刚那不过是小小的开个玩笑）

题目描述

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

输入格式

第1行整数n。

第2行到n+1行每行包含一个整数 next_i 。

输出格式

n行，第i行包含一个整数，表示第i只奶牛要前往的隔间数。

样例解释

有4个隔间

隔间1要求牛到隔间1

隔间2要求牛到隔间3

隔间3要求牛到隔间2

隔间4要求牛到隔间3

牛1，从1号隔间出发，总共访问1个隔间；

牛2，从2号隔间出发，然后到三号隔间，然后到2号隔间，终止，总共访问2个隔间；

牛3，从3号隔间出发，然后到2号隔间，然后到3号隔间，终止，总共访问2个隔间；

牛4，从4号隔间出发，然后到3号隔间，然后到2号隔间，然后到3号隔间，终止，总共访问3个隔间。

　　这题诚不欺我！！

　　说是搜索，那我就是搜他！！（Tarjan什么的滚蛋）

　　暴力搜他党握手！！

方法一：爆搜就完事了

　　从这个方向来看的话，很显然，这题太水了QAQ。只要动动脑子就能想到啊。

　　题意(显而易见）:牛顺着房间指示往下跑，跑到它曾经到的房间就停。

　　那么这就意味着一定有环对吧，不然他是不会贪婪自觉的停下的。

　　然后，我们就可以开始模拟(我爱模拟啦啦啦)了。

　　我们把到过的到过的房间全部标记，并且记录一下最先到这个房间的是哪一头牛，用来区分是自环还是最后陷入他环这很重要。

　　说好的暴力，那我们就用暴力来实现这个策略（耿气），只要房间没有牛来过就搜他，然后下一个房间如果没牛到过，那这头牛就滚去那里，最后一定会遇到下一个房间曾经有牛来过.

　　无路可走了，我们这个时候就需要去判断一下：

如果是自己到过的，我们就找到了环内的一点，而且是牛最早来的点，该点的ans就被记成这个环的大小，记录下它的位置就完事了，随后这个环上的值统一为ans[;
如果是别的牛走过了，我们这头聪明二逼的牛为啥要再走一遍做同样的事情嘞傻吗，而且这个点的ans一定更新过，直接加上ans[nxt[x]]滚蛋就可以了啊。

　　说暴力过不了的出来挨打，什么你说这不是暴力??那您的认为什么是暴力呢???

　　我们是NOIP选手好吗，提高组，不是普及。

　　拿来公认的提高题的纯爆搜写法我康康，不介意打脸。

　　所以，记搜就完事了QAQ。

　放上代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;const int MA=1e5+1;
int n,now,hc;
int nxt[MA],ans[MA];
int col[MA],sum;
bool sl[MA]; int h(int x) {int dept=1;if(!sl[nxt[x]]) {sl[nxt[x]]=1;col[nxt[x]]=sum;dept+=h(nxt[x]);}else {if(col[nxt[x]]==col[x]) {hc=nxt[x];return 1;}else dept+=ans[nxt[x]];}ans[x]=dept;return dept;
}void ser(int x) {sl[x]=1;sum++;col[x]=sum;hc=0;ans[x]=h(x);if(hc>0) {now=nxt[hc];while(now!=hc) {ans[now]=ans[hc];now=nxt[now];}}return;
}int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&nxt[i]);if(i==nxt[i]) sl[i]=1;ans[i]=1;}for(int i=1;i<=n;i++) {if(!sl[i]) ser(i);cout<<ans[i]<<endl;}return 0;
}