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

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define N 100100
using namespace std;

int n,cnt,sm,last,re,st[N],dis[N],low[N],f[N],g[N],d[N];
vector <int> a[N],b[N];

void visit(int x,int par)
{
    dis[x]=low[x]=++cnt; st[++last]=x;
    for (int i=0;i<int(a[x].size());i++)
        if (!d[a[x][i]] && a[x][i]!=par)
        {
            if (dis[a[x][i]]) low[x]=min(low[x],dis[a[x][i]]);
            else visit(a[x][i],x), low[x]=min(low[x],low[a[x][i]]);
        }
    if (low[x]<dis[x]) return;
    ++sm;
    for (;;)
    {
        int y=st[last--];
        d[y]=sm;
        if (x==y) return;
    }
}

void calc(int x,int par)
{
    int extra=int(1e9),u=0;
    d[x]=0;
    if (b[x].empty() || (b[x].size()==1 && par)) return;
    for (int i=0;i<int(b[x].size());i++)
    {
        int y=b[x][i];
        if (y==par) continue;
        calc(y,x);
        u+=g[y];
        extra=min(extra,f[y]-g[y]);
    }
    g[x]=min(f[x],u+extra);
    f[par]+=min(g[x],u);
}

int main()
{
    int m,x,y;
    cin >> n >> m;
    while (m--)
    {
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for (int i=1;i<=n;i++)
        if (!d[i]) visit(i,0);
    for (int x=1;x<=n;x++)
        for (int i=0;i<int(a[x].size());i++)
            if (d[a[x][i]]!=d[x])
                b[d[x]].push_back(d[a[x][i]]);
    for (int i=1;i<=sm;i++) f[i]=g[i]=1;
    for (int i=1;i<=sm;i++)
        if (d[i]) calc(i,0), re+=g[i];
    cout << re << endl;
    return 0;
}

Code mẫu của happyboy99x

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cassert>
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;

const int N = 1e5, M = 1e5, INF = 1e9;
vector<pair<int, int> > graph[N];
bool isBridge[M], vst[N];
int discover[N], low[N], parent[N], f[N][3], ttime, n, m;

template<class T> ostream& operator << (ostream &out, const pair<T, T> &x) {
    return out << '(' << x.first << ", " << x.second << ')';
}

void enter() {
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        graph[u].push_back(make_pair(v, i));
        graph[v].push_back(make_pair(u, i));
    }
}

void dfs(int u) {
    discover[u] = low[u] = ttime++;
    for(unsigned i = 0; i < graph[u].size(); ++i) {
        int v = graph[u][i].first, e = graph[u][i].second;
        if(discover[v] == -1) {
            parent[v] = u;
            dfs(v);
            low[u] = min(low[u], low[v]);
            isBridge[e] = low[v] >= discover[v];
        } else if(v != parent[u]) {
            low[u] = min(low[u], discover[v]);
        }
    }
}

void calcF(int u) {
    vector<int> child;
    queue<int> q; q.push(u); vst[u] = true;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(unsigned i = 0; i < graph[u].size(); ++i) {
            int v = graph[u][i].first, e = graph[u][i].second;
            if(vst[v]) continue;
            if(isBridge[e]) {
                child.push_back(v);
            } else {
                q.push(v);
                vst[v] = true;
            }
        }
    }
    if(child.empty()) {
        f[u][0] = 0;        // parent[u] is in set
        f[u][1] = 1;        // u is in set
        f[u][2] = INF;      // at least one child of u is in set
    } else {
        f[u][0] = 0; f[u][1] = 1; f[u][2] = 0;
        int lambda = INF;
        for(unsigned i = 0; i < child.size(); ++i) {
            int v = child[i];
            calcF(v);
            f[u][1] += f[v][0];
            f[u][2] += min(f[v][1], f[v][2]);
            lambda = min(lambda, f[v][1] - min(f[v][1], f[v][2]));
        }
        f[u][0] = min(f[u][1], f[u][2]);
        f[u][2] += lambda;
    }
}

void solve() {
    memset(discover, -1, sizeof discover);
    memset(parent, -1, sizeof parent);
    int res = 0;
    for(int s = 0; s < n; ++s) {
        if(discover[s] == -1) {
            dfs(s);
            calcF(s);
            res += min(f[s][1], f[s][2]);
        }
    }
    cout << res << endl;
}

int main() {
#ifdef __DNK__
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(false);
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 100005;
const int oo = 1000000000;
using namespace std;
bool was[N];
int num[N], low[N], lab[N], F[3][N];
VI a[N], adj[N];
int n, m, timer, nNode;

stack<int> S;
void build(int u, int par) {
    num[u] = ++timer; low[u] = oo; S.push(u);
    int v;
    FOR(i, 0, SZ(a[u])) {
        v = a[u][i];
        if (was[v] || v == par) continue;
        if (num[v]) low[u] = min(low[u], num[v]);
        else {
            build(v, u);
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] >= num[u]) {
        ++nNode;
        do {
            v = S.top(); S.pop();
            was[v] = 1;
            lab[v] = nNode;
        } while (v != u);
    }
}

void minimize(int &a, int b) {a = a > b ? b : a;}

void DP(int u, int par) {
    was[u] = 1;
    FOR(i, 0, SZ(adj[u]))
    if (adj[u][i] != par) DP(adj[u][i], u);
    F[0][u] = 1; F[1][u] = 0;
    FOR(i, 0, SZ(adj[u])) {
        int v = adj[u][i];
        if (v == par) continue;
        F[0][u] += F[1][v];
        F[1][u] += F[2][v];
    }
    F[2][u] = F[0][u];
    FOR(i, 0, SZ(adj[u]))
    if (adj[u][i] != par)
        minimize(F[2][u], F[1][u] - F[2][adj[u][i]] + F[0][adj[u][i]]);
    minimize(F[1][u], F[0][u]);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int u, v;
    FOR(i, 0, m) {
        cin >> u >> v;
        a[u].PB(v); a[v].PB(u);
    }
    REP(i, 1, n) if (!was[i]) build(i, 0);
    REP(i, 1, n) FOR(j, 0, SZ(a[i]))
    if (lab[i] != lab[a[i][j]])
        adj[lab[i]].PB(lab[a[i][j]]), adj[lab[a[i][j]]].PB(lab[i]);
    REP(i, 1, nNode) {
        was[i] = 0;
        sort(ALL(adj[i]));
        int newSize = unique(ALL(adj[i])) - adj[i].begin();
        adj[i].resize(newSize);
    }
    int ans = 0;
    REP(i, 1, nNode) if (!was[i]) {
        was[i] = 1;
        DP(i, 0);
        ans += F[2][i];
    }
    cout << ans;
    return 0;
}

Code mẫu của RR

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

#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 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 FOREACH(it,c) for (__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define RESET(c,x) memset (c, x, sizeof (c))

#define sqr(x) ((x) * (x))
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) (c).size()

#define DEBUG(x) { cout << #x << " = " << x << endl; }
#define PR(a,n) {cout<<#a<<" = "; FOR(_,1,n) cout << a[_] << ' '; cout <<endl;}
#define PR0(a,n) {cout<<#a<<" = ";REP(_,n) cout << a[_] << ' '; cout << endl;}

using namespace std;

const double PI = 2.0 * acos (0.0);

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

template <class T> inline T MAX (T a, T b) { if (a > b) return a; return b; }
template <class T> inline T MIN (T a, T b) { if (a < b) return a; return b; }

// ptrrsn_1's template

const int MN = 100111;

int n, m, low[MN], num[MN], reg[MN], st[MN], top, now, nReg, ls[MN], sz, res;
vector< int > ke[MN], ke2[MN];
int f[3][MN];

void init() {
    memset(num, 0, sizeof num);
    memset(reg, 0, sizeof reg);
    top = now = res = 0;
    FOR(i,1,n) ke[i].clear();
}

void dfs1(int u, int fu) {
    ++now;
    low[u] = num[u] = now;
    st[++top] = u;
    ls[++sz] = u;

    REP(i,ke[u].size()) {
        int v = ke[u][i];
        if (v == fu) continue;

        if (!num[v]) {
            dfs1(v, u);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], num[v]);
    }

    if (low[u] == num[u]) {
        ++nReg;
        while (st[top] != u) {
            reg[st[top--]] = nReg;
        }
        reg[st[top--]] = nReg;
    }
}

void dfs2(int u, int fu) {
    f[0][u] = 0; // Khong to mau u, u thoa man
    f[1][u] = 1; // Co' to mau u, u thoa man
    f[2][u] = 0; // Khong to mau u, u ko thoa man, con u thoa man

    bool isLeaf = true, has = false;

    int nn = 1000111000;

    REP(i,ke2[u].size()) {
        int v = ke2[u][i];
        if (v == fu) continue;

        isLeaf = false;

        dfs2(v, u);

        if (f[0][v] < f[1][v]) {
            f[0][u] += f[0][v];
            nn = min(nn, f[1][v] - f[0][v]);
        }
        else {
            has = true;
            f[0][u] += f[1][v];
        }
        f[1][u] += min(f[0][v], min(f[2][v], f[1][v]));
        f[2][u] += min(f[0][v], f[1][v]);
    }

    if (!has) f[0][u] += nn;

    if (isLeaf) {
        f[0][u] = 1000111000;
        f[1][u] = 1;
        f[2][u] = 0;
    }
}

set< pair<int,int> > s;

void solve(int u) {
    nReg = sz = top = 0;
    dfs1(u, -1);

    // PR(reg, n);
    // PR(ls, sz);

    FOR(i,1,nReg) {
        ke2[i].clear();
    }

    s.clear();
    FOR(t,1,sz) {
        int u = ls[t];
        REP(i,ke[u].size()) {
            int v = ke[u][i];
            if (reg[u] != reg[v] && s.find(MP(reg[u], reg[v])) == s.end()) {
                ke2[reg[u]].PB(reg[v]);
                ke2[reg[v]].PB(reg[u]);

                s.insert(MP(reg[u], reg[v]));
                s.insert(MP(reg[v], reg[u]));
            }
        }
    }

    if (nReg == 1) ++res;
    else {
        dfs2(1, -1);
        res += min(f[0][1], f[1][1]);

        // PR(f[0], nReg);
        // PR(f[1], nReg);
        // PR(f[2], nReg);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        ke[u].PB(v);
        ke[v].PB(u);
    }
    FOR(i,1,n)
    if (!num[i]) {
        solve(i);
    }

    cout << res << endl;
    return 0;
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define MAX   200200
#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++)
#define fi   first
#define se   second
using namespace std;
const int INF=(int)1e6+7;
typedef pair<int,int> ii;
vector<ii> g[MAX];
vector<int> t[MAX];
bool blk[MAX];
bool isbr[MAX];
int m,n,nc,cnt;
int p[MAX];
int id[MAX];
int low[MAX];
int num[MAX];
int f[MAX][4];
int min(int x,int y) {
    if (x<y) return (x); else return (y);
}
int min(int x,int y,int z) {
    return (min(x,min(y,z)));
}
int minimize(int &x,const int &y) {
    if (x>y) x=y;
}
int toblock(int id) {
    if (id%2==0) return (id-1); else return (id+1);
}
void loadgraph(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    FOR(i,1,m) {
        int u,v;
        scanf("%d",&u);
        scanf("%d",&v);
        g[u].push_back(ii(v,2*i-1));
        g[v].push_back(ii(u,2*i));
    }
}
void visit(int u) {
    cnt++;
    low[u]=n+7;
    num[u]=cnt;
    FORE(it,g[u]) if (!blk[it->se]) {
        int v=it->fi;
        if (num[v]==0) {
            blk[toblock(it->se)]=true;
            visit(v);
            isbr[it->se]=(low[v]>num[u]);
            isbr[toblock(it->se)]=(low[v]>num[u]);
            minimize(low[u],low[v]);
        }
        else minimize(low[u],num[v]);
    }
}
void BFS(int s,int no) {
    queue<int> q;
    while (!q.empty()) q.pop();
    q.push(s);
    id[s]=no;
    while (!q.empty()) {
        int u=q.front(); q.pop();
        FORE(it,g[u]) if (!isbr[it->se])
            if (id[it->fi]==0) {
                id[it->fi]=no;
                q.push(it->fi);
            }
    }
}
void loadtree(void) {
    FOR(i,1,n) if (num[i]==0) visit(i);
    FOR(i,1,n) if (id[i]==0) {
        nc++;
        BFS(i,nc);
    }
    FOR(i,1,n) FORE(it,g[i]) if (isbr[it->se]) {
        isbr[toblock(it->se)]=false;
        t[id[i]].push_back(id[it->fi]);
        t[id[it->fi]].push_back(id[i]);
    }
    memset(p,-1,sizeof p);
}
void dpvisit(int u) {
    bool leaf=true;
    FORE(it,t[u]) if (*it!=p[u]) {
        int v=*it;
        p[v]=u;
        dpvisit(v);
        leaf=false;
    }
    if (leaf) {
        f[u][0]=0;
        f[u][1]=INF;
        f[u][2]=1;
        return;
    }
    FORE(it,t[u]) if (*it!=p[u]) {
        if (f[*it][1]<INF) f[u][0]+=f[*it][1];
        else {
            f[u][0]=INF;
            break;
        }
    }
    bool ok=false;
    int minadd=INF;
    FORE(it,t[u]) if (*it!=p[u]) {
        f[u][1]+=min(f[*it][1],f[*it][2]);
        if (f[*it][2]<=f[*it][1]) ok=true;
        minimize(minadd,f[*it][2]-f[*it][1]);
    }
    if (!ok) f[u][1]+=minadd;
    FORE(it,t[u]) if (*it!=p[u]) f[u][2]+=min(f[*it][0],f[*it][1],f[*it][2]);
    f[u][2]++;
}
void process(void) {
    int res=0;
    FOR(i,1,nc) if (p[i]<0) {
        p[i]=0;
        dpvisit(i);
        res+=min(f[i][1],f[i][2]);
    }
    printf("%d",res);
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
#endif
    loadgraph();
    loadtree();
    process();
    return 0;
}