CRITICAL - Thành phố trọng yếu

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      maxn=20010;
      maxm=200010;
var m,n,dem,s,sm:longint;
    a:array[1..maxm*2] of longint;
    sl,cur,pos,num,low,cha,d,mien:array[1..maxn] of longint;
    b:array[1..maxm,0..1] of longint;
    free:array[1..maxn] of boolean;
    re:real;

procedure rf;
var i:longint;
begin
     read(n,m);
     for i:=1 to m do
     begin
          read(b[i,0],b[i,1]);
          inc(sl[b[i,0]]); inc(sl[b[i,1]]);
     end;
     pos[1]:=1; cur[1]:=1;
     for i:=2 to n+1 do
     begin
          pos[i]:=pos[i-1]+sl[i-1]; cur[i]:=pos[i];
     end;
     for i:=1 to m do
     begin
          a[cur[b[i,0]]]:=b[i,1];
          inc(cur[b[i,0]]);
          a[cur[b[i,1]]]:=b[i,0];
          inc(cur[b[i,1]]);
     end;
end;

function min(u,v:longint):longint;
begin
     if u<v then min:=u else min:=v;
end;

procedure visit(x,y:longint;var s:longint);
var i,t,nm,sum,sq,u:longint;
begin
     inc(dem); num[x]:=dem; low[x]:=n+1;
     s:=0; nm:=0; sum:=0; sq:=0;t:=0; u:=0;
     for i:=pos[x] to pos[x+1]-1 do
         if a[i]<>y then
         begin
              if cha[a[i]]<>0 then low[x]:=min(low[x],num[a[i]])
              else
              begin
                   cha[a[i]]:=x;
                   visit(a[i],x,t);
                   low[x]:=min(low[x],low[a[i]]);
                   s:=s+t;
                   if low[a[i]]>=num[x] then
                   begin
                        sum:=sum+t;
                        sq:=sq+t*t;
                   end else u:=u+t;
              end;
         end;
     s:=s+1;
     t:=mien[d[x]]-s+u;
     sum:=sum+t;
     sq:=sq+t*t;
     re:=re+(sum*sum-sq) div 2;
end;

procedure dfs(x,y:longint);
var i:longint;
begin
     d[x]:=sm; inc(mien[sm]); free[x]:=true;
     for i:=pos[x] to pos[x+1]-1 do
         if not free[a[i]] and (a[i]<>y) then dfs(a[i],x);
end;

procedure pr;
var i,j:longint;
begin
     dem:=0; sm:=0;
     for i:=1 to n do
         if not free[i] then
         begin
              inc(sm);
              dfs(i,0);
         end;
     for i:=1 to n do
         if num[i]=0 then
         begin
              cha[i]:=-1;
              visit(i,0,s);
         end;
     writeln(re/n:0:2);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Download