Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

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.

Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
const int N = 20000 + 5, INF = 1000000000;
vector<vector<int> > g;
int n, m, d[N], low[N], r[N], timed;
bool vst[N];

void enter() {
    scanf("%d%d",&n,&m); g.resize(n);
    for(int i = 0; i < m; ++i) {
        int u, v; scanf("%d%d",&u,&v);
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
}

int sqr(const int &x) { return x * x; }
long long res;

void dfs(int u, int p, int nnode) {
    d[u] = ++timed; r[u] = 1; low[u] = INF;
    int rem = nnode - 1, add = sqr(nnode - 1), nchild = 0;
    TR(g[u], it) {
        int v = *it;
        if(d[v]) { if(v != p) low[u] = min(low[u], d[v]); }
        else {
            dfs(v, u, nnode); low[u] = min(low[u], low[v]);
            r[u] += r[v]; ++nchild;
            if((p == -1 && nchild > 1 || p != -1) && low[v] >= d[u])
                rem -= r[v], add -= sqr(r[v]);
        }
    }
    if(p == -1 && nchild > 1) rem -= r[g[u][0]], add -= sqr(r[g[u][0]]);
    res += add - sqr(rem);
}

int bfs(int u) {
    int res = 0; queue<int> q; q.push(u); vst[u] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop(); ++res;
        TR(g[u], v) if(vst[*v] == 0) vst[*v] = 1, q.push(*v);
    }
    return res;
}

void solve() {
    for(int u = 0; u < n; ++u) if(vst[u] == 0) dfs(u, -1, bfs(u));
    printf("%.2lf\n", (double) res / (2*n));
}

int main() {
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

int n, m, cc;
int Time;
int was[N];
int par[N];
int root[N];
int num[N], low[N];
int Size[N];
long long ans[N];
vector<int> a[N];

void dfs(int u) {
    was[u] = cc; num[u] = ++Time; low[u] = N; Size[u] = 1;
    for (int v : a[u]) if (v != par[u]) {
        if (was[v]) {
            low[u] = min(low[u], num[v]);
        } else {
            par[v] = u;
            dfs(v);
            low[u] = min(low[u], low[v]);
            Size[u] += Size[v];
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        a[u].push_back(v); a[v].push_back(u);
    }
    for (int u = 1; u <= n; ++u) {
        sort(a[u].begin(), a[u].end());
        a[u].resize(unique(a[u].begin(), a[u].end()) - a[u].begin());
    }
    for (int i = 1; i <= n; ++i) if (!was[i]) {
        ++cc;
        root[cc] = i;
        dfs(i);
    }
    for (int u = 1; u <= n; ++u) {
        long long cur = 0, sizePar = Size[root[was[u]]] - 1;
        for (int v : a[u]) if (par[v] == u && low[v] >= num[u]) {
            ans[u] += cur * Size[v];
            cur += Size[v];
            sizePar -= Size[v];
        }
        if (sizePar) {
            ans[u] += cur * sizePar;
        }
    }
    long long sum = 0;
    for (int u = 1; u <= n; ++u) sum += ans[u];
    cout << setprecision(2) << fixed << (long double)sum / n << endl;
    return 0;
}

Code mẫu của RR

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.

Code mẫu của skyvn97

#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#define MAX   20020
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
typedef long long ll;
vector<int> g[MAX];
int low[MAX];
int num[MAX];
int ncp[MAX];
int nc[MAX];
int sz[MAX];
int n,m,cnt;
ll sp;
void minimize(int &x,const int &y) {
    if (x>y) x=y;
}
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    REP(i,m) {
        int u,v;
        scanf("%d",&u);
        scanf("%d",&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }   
}
ll sumproduct(const vector<int> &v) {
    int sumall=0;
    ll sumsqr=0LL;
    FORE(it,v) {
        sumall+=*it;
        sumsqr+=1LL*(*it)*(*it);
    }
    return (1LL*sumall*sumall-sumsqr)/2;
}
int BFS(int s,int id) {
    queue<int> q;
    while (!q.empty()) q.pop();
    ncp[s]=id;
    q.push(s);
    int ret=1;
    while (!q.empty()) {
        int u=q.front();q.pop();
        FORE(it,g[u]) if (ncp[*it]==0) {
            ncp[*it]=id;
            q.push(*it);
            ret++;
        }
    }
    return (ret);
}
void visit(int u) {
    vector<int> nchild=vector<int>();
    int nrest=0;
    cnt++;  
    low[u]=n+7;
    num[u]=cnt;
    FORE(it,g[u]) {
        int v=*it;
        if (num[v]==0) {
            visit(v);
            nc[u]+=nc[v];
            if (low[v]>=num[u]) nchild.push_back(nc[v]);
            else nrest+=nc[v];
            minimize(low[u],low[v]);
        }
        else minimize(low[u],num[v]);
    }
    nc[u]++;
    nrest+=sz[ncp[u]]-nc[u];
    nchild.push_back(nrest);
    sp+=sumproduct(nchild);
}
void process(void) {
    int tmp=0;
    FOR(i,1,n) if (ncp[i]==0) {
        tmp++;
        sz[tmp]=BFS(i,tmp);
    }
    FOR(i,1,n) if (num[i]==0) visit(i);
    printf("%.2lf",1.0*sp/n);
}
int main(void) {
    loadgraph();
    process();
    return 0;
}