1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 419 Solved: 232
[Submit][Status][Discuss]
Description
每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N(1≤N≤100000)个牛棚里转悠，来采集糖果．她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果． 农场不大，所以约翰要想尽法子让奶牛们得到快乐．他给每一个牛棚设置了一个“后继牛棚”．牛棚i的后继牛棚是Xi．他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果．事实上这是一种有点欺骗意味的手段，来节约他的糖果． 第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果．
Input
第1行输入N，之后一行一个整数表示牛棚i的后继牛棚Xi，共N行．
Output
共N行，一行一个整数表示一只奶牛可以采集的糖果数量．
Sample Input
4 //有四个点
1 //1有一条边指向1
3 //2有一条边指向3
2 //3有一条边指向2
3
1 //1有一条边指向1
3 //2有一条边指向3
2 //3有一条边指向2
3
INPUT DETAILS:
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
Sample Output
1
2
2
3
2
2
3
HINT
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.
Source
题解：N个月前刚刚开BZOJ权限的时候，看了这道题，毫无思路，甚至想过暴搜（实际上此题求的就是各点所能到达的点的个数），但是要是 \( N \leq 1000 \) 的话倒还说的过去，\( O({N}^{2} ) \) 的复杂度毕竟。。。
实际上现在做起来也不难，就是个tarjan算法，将复杂图缩点转化为拓扑图，然后慢慢递推即可A掉。。。
/**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ type
point=^node;
node=record
g:longint;
next:point;
end;
map=array[..] of point;
var
i,j,k,l,m,n,h,t,ans:longint;
low,dfn,f,b,d,e:array[..] of longint;
a,c:map;p:point;
ss,s:array[..] of boolean;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
procedure add(x,y:longint;var a:map);
var p:point;
begin
new(p);p^.g:=y;
p^.next:=a[x];a[x]:=p;
end;
procedure tarjan(x:longint);
var p:point;
begin
inc(h);low[x]:=h;dfn[x]:=h;
inc(t);f[t]:=x;
ss[x]:=true;s[x]:=true;
p:=a[x];
while p<>nil do
begin
if not(s[p^.g]) then
begin
tarjan(p^.g);
low[x]:=min(low[x],low[p^.g]);
end
else if ss[p^.g] then low[x]:=min(low[x],dfn[p^.g]);
p:=p^.next;
end;
if low[x]=dfn[x] then
begin
inc(ans);
while f[t+]<>x do
begin
ss[f[t]]:=false;
b[f[t]]:=ans;
dec(t);
end;
end;
end;
procedure dfs(x:longint);
var p:point;
begin
p:=c[x];
e[x]:=d[x];
while p<>nil do
begin
if e[p^.g]= then dfs(p^.g);
e[x]:=e[x]+e[p^.g];
p:=p^.next;
end;
end;
begin
readln(n);
for i:= to n do a[i]:=nil;
for i:= to n do
begin
readln(j);
add(i,j,a);
end;
fillchar(s,sizeof(s),false);
fillchar(ss,sizeof(ss),false);
fillchar(low,sizeof(low),);
fillchar(dfn,sizeof(dfn),);
fillchar(f,sizeof(f),);
h:=;t:=;ans:=;
for i:= to n do
if b[i]= then tarjan(i);
fillchar(d,sizeof(d),);
for i:= to n do inc(d[b[i]]);
for i:= to ans do c[i]:=nil;
for i:= to n do
begin
p:=a[i];
while p<>nil do
begin
if b[i]<>b[p^.g] then add(b[i],b[p^.g],c);
p:=p^.next;
end;
end;
fillchar(e,sizeof(e),);
for i:= to ans do
if e[i]= then dfs(i);
for i:= to n do
writeln(e[b[i]]);
readln;
end.