1123: [POI2008]BLO
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 359 Solved: 126
[Submit][Status][Discuss]
Description
Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。
Input
输入n<=100000 m<=500000及m条边
Output
输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。
Sample Input
5 5
1 2
2 3
1 3
3 4
4 5
1 2
2 3
1 3
3 4
4 5
Sample Output
8
8
16
14
8
8
16
14
8
连通性的应用，根据树边与回边的性质，一个点被去掉时，影响的是存在回边的子树与不存在回边的子树，以及祖先，tarjan时分下类即可。
主要还是想抱怨下oj，原以为只有poj会数组开小出现wa，tle的情况，没想到衡八也是，调了我老久。
{$M 100000000}
var size,tail,rel,low:array[1..1000005]of longint;
ans:array[1..1000005]of int64;
next,sora:array[1..5000005]of longint;
m,time,ss:longint;
n:int64;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y)
end;
procedure dfs(x:longint);
var i,ne:longint;
ans1:int64;
begin
inc(time);rel[x]:=time;low[x]:=time;i:=x;size[x]:=1;
ans1:=0;
while next[i]<>0 do begin
i:=next[i];ne:=sora[i];
if rel[ne]<1073741819 then low[x]:=min(low[x],rel[ne])
else begin
dfs(ne);
size[x]:=size[x]+size[ne];
if low[ne]<low[x] then low[x]:=low[ne];
if low[ne]>=rel[x] then begin
ans[x]:=ans[x]+ans1*size[ne];
ans1:=ans1+size[ne]
end
end
end;
ans[x]:=ans[x]+(n-ans1-1)*ans1+n-1
end;
procedure origin;
var i:longint;
begin
for i:=1 to n do tail[i]:=i;ss:=n;
end;
procedure link(x,y:longint);
begin
inc(ss);next[tail[x]]:=ss;tail[x]:=ss;sora[ss]:=y;
inc(ss);next[tail[y]]:=ss;tail[y]:=ss;sora[ss]:=x
end;
procedure init;
var i,x,y:longint;
begin
readln(n,m);
origin;
for i:=1 to m do begin
readln(x,y);link(x,y)
end;
fillchar(rel,sizeof(rel),127);fillchar(low,sizeof(low),127);
time:=0;
dfs(1);
for i:=1 to n do writeln(ans[i]<<1)
end;
begin
assign(input,'1123.in');reset(input);
init;
close(input)
end.