今天我来给大家带来一片蒟蒻题解 ~~真香
LGOJ P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm
题目描述
每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。
由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。
FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。
在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。
输入格式
第1行 整数n。
第2行到n+1行 每行包含一个整数 next_i 。
输入输出样例
in 1:
4
1
3
2
3
out 1:
1
2
2
3
思路引导：
clearly，我们可以发现cow是一圈圈走的。看到圈我们想到什么？对，是环。怎样快速地判断一根环呢？不会是O(n)查找吧。。。这时，我们就可以使用一种特别简便的数据结构，就是并查集。并查集的算法研究，可以追溯到20世纪30年代，上海黑帮黑吃黑。不同于黑帮互殴的是，并查集的帮派只看coder的意思，没有流血伤亡，全是光荣革命，通过coder的淳淳教导（启发式搜索），还可以加快黑帮合并的速度，还有一种更加strong的办法，叫做路径压缩，可以是黑帮的每个人都直接听命于老大，时间复杂度直接降到了常数级别！这么好的方法，我们想到了，当然要用一用啦。在这道题中，我们的用法又略有不同。话不多说，上代码。代码有详解。
/*
Name: Trick or Treat on the Farm
Author: Jack
Date: 05-04-19 20:38
Description:
节点：房间。
环：cow按指示走直到不得不停时走过节点组成的环
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+;
int dfn[maxn],inloop[maxn],col[maxn],nxt[maxn],loopsize[maxn];
//dfn:时间戳，记录访问到当前节点时的时间，辅助inloop
//inloop:入环时间戳，记录访问到这个环时，时间是多少
//col:并查集，记录每个节点的祖先。本题较特殊，不是用具体的节点作为祖先，而是用一个概念“牛”，将牛的编号作为祖先，所以并查集一般的操作都用不了。As the matter of fact，本题是可以用节点作为祖先解决的。但那样思路会有点卡壳，所以还是hack掉了。
//nxt：每个节点连接的下一个节点
//loopsize：环的节点个数
int n;void init(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&nxt[i]);
memset(dfn,,sizeof(dfn));
memset(col,,sizeof(col));
memset(loopsize,,sizeof(loopsize));
//输入以及都清空。
}
void work(){
for(int now=;now<=n;now++){//按每只牛循环。
for(int i=now,cnt=;;i=nxt[i],cnt++){
//按访问顺序访问
if(!col[i]){
col[i]=now;//这个房间归这头牛了
dfn[i]=cnt;//时间戳就是cnt
}
else if(col[i]==now){
//如果回到了自己的地盘
loopsize[now]=cnt-dfn[i];
//环的大小=访问最后一个点的时间-访问第一个点的时间
inloop[now]=dfn[i];
//入环时间=访问第一个点的时间
printf("%d\n",cnt);
break;
} else {
//如果来到了他人的领地，就扩充自己的领地
loopsize[now]=loopsize[col[i]];
//环的大小=他人领地的大小
inloop[now]=cnt+max(inloop[col[i]]-dfn[i],);
//入环时间=访问最后一个点的时间加后面这一串，留作思考题，自己想
printf("%d\n",inloop[now]+loopsize[now]);
break;
}
}
}
}
int main(){
init();
work();
return ;
}
完美结束OK，谢谢观赏，各位看官觉得写得好的点个赞呗~~