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

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
const
  MAXN=20111;

type
  list=^node;
  node=record
        u:longint;
        next:list;
  end;

procedure add(u:longint; var a:list);
    var
      p:list;
    begin
      new(p); p^.u:=u;
      p^.next:=a; a:=p;
    end;

var
  n,m,u,v,cnt,sl:longint;
  ke:array[1..MAXN] of list;
  res:int64;
  w,low,num,reg,father,count:array[1..MAXN] of longint;

procedure dfs1(u:longint);
    var
      v:longint;
      p:list;
    begin
      reg[u]:=sl; w[u]:=1;

      inc(cnt);
      low[u]:=cnt; num[u]:=cnt;

      p:=ke[u];
      while p<>nil do
        begin
          v:=p^.u; p:=p^.next;
          if v=father[u] then continue;

          if num[v]=0 then
            begin
              father[v]:=u;
              dfs1(v);
              low[u]:=min(low[u],low[v]);
              inc(w[u],w[v]);
            end
          else low[u]:=min(low[u],num[v]);
        end;
    end;

procedure dfs2(u:longint);
    var
      v,tmp:longint;
      p:list;
    begin
      p:=ke[u]; tmp:=count[reg[u]]-1;
      while p<>nil do
        begin
          v:=p^.u; p:=p^.next;
          if father[v]<>u then continue;
          dfs2(v);

          //Cac dinh thuoc cay con goc v khong di duoc len tren dinh u
          if low[v]>=num[u] then
            begin
              tmp:=tmp-w[v];
              res:=res+int64(w[v])*tmp;
            end;
        end;
    end;

begin
  read(n,m);
  for m:=1 to m do
    begin
      read(u,v);
      add(u,ke[v]);
      add(v,ke[u]);
    end;

  sl:=0;
  for u:=1 to n do
  if num[u]=0 then
    begin
      cnt:=0;
      inc(sl);
      dfs1(u);
    end;

  for u:=1 to n do
    inc(count[reg[u]]);

  for u:=1 to n do
    if father[u]=0 then
      dfs2(u);

  writeln(res/n:0:2);
end.

Download