LGOJP2921[USACO08DEC]在农场万圣节TrickorTreatontheFarm

/*Name: Trick or Treat on the Farm Author: JackDate: 05-04-19 20:38Description:
　　　　节点&＃xff1a;房间。
　　　　环&＃xff1a;cow按指示走直到不得不停时走过节点组成的环
*/
#include
using namespace std;
const int maxn &＃61; 1e6&＃43;5;
int dfn[maxn],inloop[maxn],col[maxn],nxt[maxn],loopsize[maxn];
//dfn:时间戳&＃xff0c;记录访问到当前节点时的时间&＃xff0c;辅助inloop
//inloop:入环时间戳&＃xff0c;记录访问到这个环时&＃xff0c;时间是多少
//col:并查集&＃xff0c;记录每个节点的祖先。本题较特殊&＃xff0c;不是用具体的节点作为祖先&＃xff0c;而是用一个概念“牛”&＃xff0c;将牛的编号作为祖先&＃xff0c;所以并查集一般的操作都用不了。As the matter of fact&＃xff0c;本题是可以用节点作为祖先解决的。但那样思路会有点卡壳&＃xff0c;所以还是hack掉了。
//nxt&＃xff1a;每个节点连接的下一个节点
//loopsize&＃xff1a;环的节点个数
int n;void init(){scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&nxt[i]);memset(dfn,0,sizeof(dfn));memset(col,0,sizeof(col));memset(loopsize,0,sizeof(loopsize));//输入以及都清空。
}
void work(){for(int now&＃61;1;now<&＃61;n;now&＃43;&＃43;){//按每只牛循环。for(int i&＃61;now,cnt&＃61;0;;i&＃61;nxt[i],cnt&＃43;&＃43;){
　　　　　　　　//按访问顺序访问if(!col[i]){col[i]&＃61;now;//这个房间归这头牛了dfn[i]&＃61;cnt;//时间戳就是cnt}else if(col[i]&＃61;&＃61;now){//如果回到了自己的地盘
　　　　　　　　　 loopsize[now]&＃61;cnt-dfn[i];
　　　　　　　　　 //环的大小&＃61;访问最后一个点的时间-访问第一个点的时间inloop[now]&＃61;dfn[i];
　　　　　　　　　 //入环时间&＃61;访问第一个点的时间printf("%d\n",cnt);break;} else {
　　　　　　　　　 //如果来到了他人的领地&＃xff0c;就扩充自己的领地loopsize[now]&＃61;loopsize[col[i]];//环的大小&＃61;他人领地的大小
　　　　　　　　　 inloop[now]&＃61;cnt&＃43;max(inloop[col[i]]-dfn[i],0);
　　　　　　　　　 //入环时间&＃61;访问最后一个点的时间加后面这一串&＃xff0c;留作思考题&＃xff0c;自己想

　　　　　　　　　 printf("%d\n",inloop[now]&＃43;loopsize[now]);
　　　　　　　　　 break;
　　　　　　　}
}
　　　　}
}

int main(){
　　 init();
　　 work();
　　 return 0;
}
完美结束