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

uses math;
var n,m,i,j,cnt,cau,khop:longint;
    p,low,num,cha,con:array[1..10010] of longint;
    a,b,c:array[1..100010] of longint;
    d:array[1..10010] of boolean;

procedure visit(x,y:longint);
var i:longint;
begin
     inc(cnt); num[x]:=cnt; low[x]:=cnt;
     cha[x]:=y;
     for i:=p[x]+1 to p[x+1] do
         if a[i]<>y then
         begin
              if num[a[i]]>0 then low[x]:=min(low[x],num[a[i]])
              else
              begin
                   visit(a[i],x);
                   low[x]:=min(low[x],low[a[i]]);
              end;
         end;
end;

begin
     read(n,m);
     for i:=1 to m do
     begin
          read(b[i],c[i]);
          inc(p[b[i]]);
          inc(p[c[i]]);
     end;
     for i:=2 to n+1 do inc(p[i],p[i-1]);
     for i:=1 to m do
     begin
          a[p[b[i]]]:=c[i];
          dec(p[b[i]]);
          a[p[c[i]]]:=b[i];
          dec(p[c[i]]);
     end;
     for i:=1 to n do
         if cha[i]=0 then visit(i,-1);
     for i:=1 to n do
         if cha[i]>0 then inc(con[cha[i]]);
     for i:=1 to n do
     begin
          j:=cha[i];
          if j<0 then continue;
          if low[i]>=num[i] then inc(cau);
          if d[j] then continue;
          if (low[i]>=num[j]) and ((cha[j]<>-1) or (con[j]>1)) then
          begin
               d[j]:=true; inc(khop);
          end;
     end;
     writeln(khop,' ',cau);
end.

Code mẫu của happyboy99x

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

const int N = 10005;
int n, m, cut, bridge, t, d[N], low[N];
vector<vector<int> > g;

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);
    }
}

void dfs(int u, int p) {
    low[u] = d[u] = ++t; int iscut = 0, nchild = 0;
    for(vector<int>::iterator v = g[u].begin(); v != g[u].end(); ++v) 
        if(d[*v] == 0) {
            ++nchild; dfs(*v, u); low[u] = min(low[u], low[*v]);
            if(low[*v] >= d[u] && p != -1 || nchild == 2 && p == -1) iscut = 1;
            if(low[*v] >= d[*v]) ++bridge;
        } else if(*v != p) low[u] = min(low[u], d[*v]);
    cut += iscut;
}

void solve() {
    for(int u = 0; u < n; ++u) if(d[u] == 0) dfs(u, -1);
    printf("%d %d\n", cut, bridge);
}

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

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 10005;
const int oo = 123456789;
using namespace std;
vector<int> a[N];
int par[N], low[N], num[N], nchild[N];
bool cut[N];
int m, n, Time, bridge, art;

void DFS(int u) {
    num[u] = ++Time;
    low[u] = n+1;
    int i, v;
    for(i=0; i<a[u].size(); i++) {
        v = a[u][i];
        if (v == par[u]) continue;
        if (par[v] == 0) {
            nchild[u]++;
            par[v] = u;
            DFS(v);
            low[u] = min(low[u], low[v]);
        }
        else
            low[u] = min(low[u], num[v]);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    int i, u, v;
    for(i=1; i<=m; i++) {
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(i=1; i<=n; i++)
    if (par[i] == 0) {
        par[i] = -1;
        DFS(i);
    }
    //bridges
    for(v=1; v<=n; v++) {
        u = par[v];
        if (u != -1 && low[v] >= num[v]) bridge++;
    }
    for(v=1; v<=n; v++)
    if (par[v] != -1) {
        u = par[v];
        if (low[v] >= num[u])
            cut[u] = cut[u] || (par[u] != -1) || (nchild[u] >= 2);
    }
    for(i=1; i<=n; i++)
        if (cut[i]) art++;
    printf("%d %d", art, bridge);
    return 0;
}

Code mẫu của RR

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <set>
#include <queue>
#include <stack>
#include <memory.h>
#include <cassert>
#include <sstream>

#define oo 1000111000
#define PI acos(-1.0)

#define FOR(i,a,b) for(int i = (a), _b = (b); i <= _b; i++)
#define FORD(i,a,b) for(int i = (a), _b = (b); i >= _b; i--)
#define REP(i,n) for(int i = 0, _n = (n); i < _n; i++)
#define REPD(i,n) for(int i = (n) - 1; i >= 0; i--)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SIZE(c) (c).size()
#define RESET(c,x) memset(c,x,sizeof(c))

using namespace std;

typedef pair <int, int> PII;
typedef long long LL;

inline void OPEN(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#define MAXV 100000

int V;
vector <int> G[MAXV + 5];

int dfs_low[MAXV + 5], dfs_num[MAXV + 5], dfs_parent[MAXV + 5];
int dfsNumberCounter, dfsRoot, rootChildren;
bool articulation_vertex[MAXV + 5];
int nBridge, nAp;

void articulationPointAndBridge(int u) {
    dfs_low[u] = dfs_num[u] = dfsNumberCounter++;
    REP (j, SIZE(G[u])) {
        int v = G[u][j];
        if (dfs_num[v] == -1) {
            dfs_parent[v] = u;
            if (u == dfsRoot) rootChildren++;
            articulationPointAndBridge(v);
            if (dfs_low[v] >= dfs_num[u])
                articulation_vertex[u] = true;
            if (dfs_low[v] > dfs_num[u])
                ++nBridge;
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);
        } else if (v != dfs_parent[u])
            dfs_low[u] = min(dfs_low[u], dfs_num[v]);
    }
}

int main() {
    scanf("%d", &V);
    int m; scanf("%d", &m);
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        --u; --v;
        G[u].PB(v);
        G[v].PB(u);
    }

    dfsNumberCounter = 0; RESET(dfs_num, -1); RESET(dfs_low, 0);
    RESET(dfs_parent, 0); RESET(articulation_vertex, 0);
    REP (i, V) if (dfs_num[i] == -1) {
        dfsRoot = i; rootChildren = 0;
        articulationPointAndBridge(i);
        articulation_vertex[dfsRoot] = (rootChildren > 1);
    }
    REP (i, V) if (articulation_vertex[i])
        ++nAp;
    printf("%d %d\n", nAp, nBridge);
    return 0;
}

Code mẫu của skyvn97

#include<set>
#include<cstdio>
#include<vector>
#include<cstring>
#define MAX   10101
using namespace std;
typedef pair<int,int> ii;
vector<int> g[MAX];
set<ii> bl;
int m,n;
int low[MAX];
int num[MAX];
int nch[MAX];
bool cutv[MAX];
int cnt;
int nb,nc;
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    int i,u,v;
    for (i=1;i<=n;i=i+1) g[i].clear();
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }       
}
int min(const int &x,const int &y) {
    if (x<y) return (x); else return (y);
}
void visit_bridge(const int &u) {
    int i,v;
    cnt++;
    num[u]=cnt;
    low[u]=n+1;
    for (i=0;i<g[u].size();i=i+1) {     
        v=g[u][i];
        if (bl.find(ii(u,v))!=bl.end()) continue;
        bl.insert(ii(v,u));
        if (num[v]==0) {
            visit_bridge(v);
            if (low[v]>num[u]) nb++;
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],num[v]);
    }
}
void count_bridge(void) {
    memset(low,0,sizeof low);
    memset(num,0,sizeof num);
    bl.clear();
    nb=0;
    cnt=0;
    int i;
    for (i=1;i<=n;i=i+1)
        if (num[i]==0) visit_bridge(i);
    printf("%d",nb);
}
void visit_cutvert(const int &u) {
    int i,v;
    cnt++;
    num[u]=cnt;
    low[u]=n+1;
    cutv[u]=false;
    for (i=0;i<g[u].size();i=i+1) {
        v=g[u][i];
        if (num[v]==0) {
            nch[u]++;
            visit_cutvert(v);
            cutv[u]=cutv[u]||(low[v]>=num[u]);
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],num[v]);
    }
}
void count_cutvert(void) {
    memset(low,0,sizeof low);
    memset(num,0,sizeof num);
    memset(nch,0,sizeof nch);
    nc=0;
    cnt=0;
    int i;
    for (i=1;i<=n;i=i+1) {
        if (num[i]==0) {    
            visit_cutvert(i);
            if (nch[i]<2) cutv[i]=false;
        }
    }
    for (i=1;i<=n;i=i+1) nc+=cutv[i];
    printf("%d ",nc);
}
int main(void) {
    loadgraph();
    count_cutvert();
    count_bridge();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <vector>
#include <cstdio>
#include <set>
using namespace std;

int n, m;
vector<pair<int,int> > ke[10010];
int num[10010], low[10010], fa[10010];
bool mark[10010], vsting[10010], khop[10010];
int tt = 0, sokhop, socau;

void dfs(int i, int edge) {
    vsting[i] = true;
    mark[i] = true;
    num[i] = tt++;
    low[i] = num[i];
    int sc = 0;
    for(int k=0;k<ke[i].size();++k) {
        int j = ke[i][k].first;
        if(!mark[j]) {
            ++sc;
            fa[j] = i;
            dfs(j, ke[i][k].second);
            low[i] = min( low[i], low[j]);
        }
        else if(ke[i][k].second != edge && vsting[j]) 
            low[i] = min( low[i], num[j]);
    }
    if(edge != -1 && low[i] == num[i]) ++socau;
    if(edge == -1) {
        if(sc > 1) khop[i] = true;
        else khop[i] = false;
    }
    if(edge != -1 && low[i] >= num[fa[i]]) khop[fa[i]] = true;
    vsting[i] = false;
}

int main() {
    scanf("%d%d", &n, &m);
    set<pair<int,int> > se;
    for(int i=0;i<m;++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        if(!se.count(make_pair(u,v))) {
        ke[u].push_back(make_pair(v,i));
        ke[v].push_back(make_pair(u,i));
        se.insert(make_pair(u,v));
        se.insert(make_pair(v,u));
        }
    }
    for(int i=1;i<=n;++i)
        if(!mark[i]) {
            dfs(i, -1);
        }
    for(int i=1;i<=n;++i) if(khop[i]) ++sokhop;
    cout << sokhop << " " << socau << endl;
    return 0;
}