洛谷P2921「USACO08DEC」题解

发表于 | 评论数： | 阅读次数：

Tarjan缩点 + 环

题目描述

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

每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N个牛棚里转 悠，来采集糖果.她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果.

农场不大，所以约翰要想尽法子让奶牛们得到快乐.他给每一个牛棚设置了一个“后继牛 棚”.牛棚i的后继牛棚是next_i 他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去， 就可以搜集到很多糖果.事实上这是一种有点欺骗意味的手段，来节约他的糖果.

第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果。

输入输出格式

输入格式

  • Line 1: A single integer: N

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

输出格式

  • 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.

INPUT & OUTPUT’s examples

Input’s e.g. #1

1
2
3
4
5
4 
1 
3 
2 
3

Output’s e.g. #1

1
2
3
4
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.

分析

我们考虑建图，把农场的房间当成节点，把第$i$号农场和$next_i$号农场连一条有向边。

题目要求中说，奶牛回到曾经去过的节点时会停止收集糖果，那么显然这张图形成了若干个环。

很容易就能想到Tarjan缩点。

然后我们思考一下每一个节点的情况。

  • 第$i$号节点可能在某一个环中。
  • 第$i$号节点还可能通过一条链和某个环相连。

那么我们首先Tarjan缩点，顺便记录每一个环的大小，那么在环内的点（第一种情况）的答案就是环的大小。

那么通过链与环相连的点（第二种情况）的答案就是这个点到环的最短距离+环的大小。

注意判断一下自环即可。

代码

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
	}
}
inline void read(int &x){
	int rt = FastIO::getint();
	x = rt;
}
inline void print(int x,bool enter){
	FastIO::putint(x);
	FastIO::flush();
	FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e5 + 10;
struct Edge{
	int next,to;
}; 
Edge Graph[MAXN << 1];
int next[MAXN],ans[MAXN];
int head[MAXN],cnt,tot,n;
int indexs,color[MAXN],LOW[MAXN],DFN[MAXN],visited[MAXN];
int STACK[MAXN],top = 1;
/* functions */
inline void Add_Edge(int from,int to){
	Graph[++cnt] = (Edge){head[from],to};
	head[from] = cnt;
} 
inline void Tarjan(int now){
	LOW[now] = DFN[now] = ++indexs;
	STACK[top] = now; top++;
	visited[now] = 1;
	for(int i=head[now];i;i=Graph[i].next){
		if(!visited[Graph[i].to]){
			Tarjan(Graph[i].to);
			LOW[now] = std::min(LOW[now],LOW[Graph[i].to]);
		}
		else if(visited[Graph[i].to] == 1)
			LOW[now] = std::min(LOW[now],DFN[Graph[i].to]);
	}
	if(DFN[now] == LOW[now]){
		tot++;
		do{
			top--;
			color[STACK[top]] = tot;
			visited[STACK[top]] = -1;
		}while(STACK[top] != now);
	}
	return;
}
inline void search(int rt,int now,int step){
	if(ans[now]) ans[rt] = ans[now] + step, return;
	else search(rt,next[now],step+1);
}
int main(int argc,char *argv[]){
	int ARC[MAXN];
	scanf("%d",&n);
	FOR(i,1,n,1){
		scanf("%d",&next[i]);
		Add_Edge(i,next[i]);
		if(next[i] == i)ans[i] = 1;
	}
	FOR(i,1,n,1){
		if(!visited[i]) Tarjan(i);
	}
	FOR(i,1,n,1) ARC[color[i]]++;
	FOR(i,1,n,1){
		if(ARC[color[i]] != 1) ans[i] = ARC[color[i]];
	}
	FOR(i,1,n,1){
		if(!ans[i]) search(i,next[i],1);
	}
	FOR(i,1,n,1) print(ans[i],false);
	return 0;
}

THE END