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

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

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 。

输出格式

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个隔间。

翻译提供者：吃葡萄吐糖

输入输出样例

输入 #1复制

4 
1 
3 
2 
3 

输出 #1复制

1 
2 
2 
3 

说明/提示

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.

题意：就是给你1-n个奶牛分别在1-n的地方每个地方都能传送到一个指定的地方问1-n每个奶牛都能经历几个地方

思路：首先把图给缩点一下然后判断独立的没形成环的点判断和环的最短距离用dfs延边一次次直到到达距离加上环的大小即为答案用数组存一下输出即可

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int maxn = 1e5+3;
int head[maxn*20], dfn[maxn], low[maxn];//dfn是时间戳low是最小的时间戳head头
int chudu[maxn], rudu[maxn], id[maxn], all[maxn];//id是染色后的点 all是染色的点数 
bool instal[maxn];int cnt, tot, gg, n, m;//instal是判断在不在栈中
stack<int>s;
int next[maxn];vector<int>ans(maxn);
struct Edge{int next, to;
}edge[maxn*20];//链式前向星存图
inline void add(int x, int y) {cnt++;edge[cnt].to = y;edge[cnt].next = head[x];head[x] = cnt;
}
//链式前向星加边
void targin(int x) {dfn[x] = low[x] = ++cnt;s.push(x);instal[x] = true;for(int i = head[x];i;i = edge[i].next) {int u = edge[i].to;if(!dfn[u]) {targin(u);low[x] = min(low[x], low[u]);}else if(instal[u]) low[x] = min(low[x], dfn[u]);}int k;if(low[x] == dfn[x]) {++gg;do{k = s.top();s.pop();instal[k] = false;id[k] = gg;all[gg]++;//id是染色gg是第一次的点把所有的一个联通快的点缩成这个点all是存的缩点的点的数量}while(x != k);}
}//强连通
void dfs(int root, int y, int step) {if(ans[y] != 0) {ans[root] = ans[y] + step;return ;}else {dfs(root, next[y], step+1);}
}
int main() {int n;scanf("%d", &n);int a;for(register int i = 1;i <= n;++i) {scanf("%d", &a);next[i] = a;add(i, a);if(i == a) {ans[i] = 1;}} for(register int j = 1;j <= n;++j) {if(!dfn[j]) {targin(j);}}//上面套强连通缩点板子for(register int j = 1;j <= n;++j) {if(all[id[j]] != 1) {ans[j] = all[id[j]];}}
//不是孤立的点的成环的肯定答案就是环的大小for(register int j = 1;j <= n;++j) {if(ans[j] == 0) {dfs(j, next[j], 1);}}
//没成环的dfs找到环的最短距离for(int i = 1;i <= n;++i) {printf("%dn", ans[i]);}//输出答案return 0;
}