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 ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 2000;
using namespace std;

struct disjoint_set {
    int P[N];
    disjoint_set() {for(int i = 0; i < N; i++) P[i] = i;}
    int at(int x) {return (x == P[x]) ? P[x] : (P[x] = at(P[x]));}
    void join(int x, int y) {P[at(x)] = at(y);}
} DS;
int id[N][N];
vector<int> a[N];
int T[N];
bool inST[N], was[N], con[N][N];
ii e[N];
int n, m;

void DFS(int u) {
    was[u] = true;
    int i, v;
    for(i = 0; i < a[u].size(); i++) {
        v = a[u][i];
        if (!was[v] && con[u][v]) {
            T[v] = u;
            DFS(v);
        }
    }
}

void PRINT() {
    for(int i = 1; i <= m; i++)
        if (inST[i]) printf("%d %d\n", e[i].X, e[i].Y);
}

int main()
{
    scanf("%d %d", &n, &m);
    int i, x, y;
    for(i = 1; i <= m; i++) {
        scanf("%d %d", &e[i].X, &e[i].Y);
        a[e[i].X].push_back(e[i].Y);
        a[e[i].Y].push_back(e[i].X);
        id[e[i].X][e[i].Y] = id[e[i].Y][e[i].X] = i;
    }
    int cnt = 0;
    for(i = 1; i <= m; i++) {
        x = DS.at(e[i].X); y = DS.at(e[i].Y);
        if (x != y) {
            con[e[i].X][e[i].Y] = con[e[i].Y][e[i].X] = true;
            inST[i] = true;
            DS.join(x, y);
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    printf("3\n"); PRINT();
    for(i = 1; i <= m; i++)
    if (!inST[i]) {
        inST[i] = true;
        con[e[i].X][e[i].Y] = con[e[i].Y][e[i].X] = false;
        int s = e[i].X, t = e[i].Y;
        DFS(s);
        inST[id[T[t]][t]] = false;
        PRINT();
        inST[id[T[t]][t]] = true;
        inST[id[T[T[t]]][T[t]]] = false;
        PRINT();
        break;
    }
    return 0;
}

Code mẫu của RR

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

vector<int> ke[1011];
int n, m, cnt;
int father[1011], getIn[1011], getOut[1011];
bool visited[1011], hasSolution = false;

int lab[1011];

int getRoot(int u) {
    if (lab[u] < 0) return u;
    else return lab[u] = getRoot(lab[u]);
}

void merge(int u, int v) {
    u = getRoot(u);
    v = getRoot(v);
    lab[u] += lab[v];
    lab[v] = u;
}

vector<int> cycle;
bool inCycle[1011];

void find(int x) {
    memset(lab, -1, sizeof lab);
    for(int i = 0; i < cycle.size(); ++i)
        if (i != x) {
            int j = (i + 1) % cycle.size();
            int u = cycle[i], v = cycle[j];

            if (getRoot(u) != getRoot(v)) {
                cout << u << ' ' << v << endl;
                merge(u, v);
        }
    }

    for(int u = 1; u <= n; ++u) {
        for(int i = 0; i < ke[u].size(); ++i) {
            int v = ke[u][i];
            if (getRoot(u) != getRoot(v)) {
                cout << u << ' ' << v << endl;
                merge(u, v);
            }
        }
    }
}

void dfs(int u) {
    getIn[u] = ++cnt;
    visited[u] = true;
    for(int i = 0; i < ke[u].size(); ++i) {
        int v = ke[u][i];
        if (v == father[u]) continue;

        if (!visited[v]) {
            father[v] = u;
            dfs(v);
        } else {
            if (!getOut[v]) {
                cycle.push_back(v);
                inCycle[v] = true;

                int x = u;
                while (!inCycle[x]) {
                    cycle.push_back(x);
                    inCycle[x] = true;

                    x = father[x];
                }

                if (!hasSolution) {
                    hasSolution = true;
                    cout << 3 << endl;
                    find(0);
                    find(1);
                    find(2);
                }
            }
        }
    }
    getOut[u] = ++cnt;
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }

    dfs(1);
}

Code mẫu của skyvn97

#include<cstdio>
#include<queue>
#include<vector>
#define MAX   2222
#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;
typedef pair<int,int> ii;
inline int nextInt(void) {
    int x;
    scanf("%d",&x);
    return (x);
}
class DSU {
    private:
    vector<int> up;
    int find(int x) {
        if (up[x]<0) return (x);
        up[x]=find(up[x]);
        return (up[x]);
    }
    public:
    DSU() {}
    DSU(int n) {
        up.assign(n+7,-1);
    }
    bool join(int a,int b) {
        int x=find(a);
        int y=find(b);
        if (x==y) return (false);
        up[y]=x;
        return (true);
    }
};
ii edge[MAX];
vector<int> g[MAX];
vector<int> cyc;
int n,m;
bool vst[MAX];
int p[MAX];
void loadgraph(void) {
    n=nextInt();
    m=nextInt();
    FOR(i,1,m) {
        int u=nextInt();
        int v=nextInt();
        edge[i]=ii(u,v);
        g[u].push_back(i);
        g[v].push_back(i);
    }
}
void bfs(int s,int f,int blk) {
    queue<int> q;
    vst[s]=true;
    q.push(s);
    while (!q.empty()) {
        int u=q.front();q.pop();
        if (u==f) return;
        FORE(it,g[u]) if (*it!=blk) {
            int v=edge[*it].fi^edge[*it].se^u;
            if (!vst[v]) {
                vst[v]=true;
                p[v]=*it;
                q.push(v);
            }
        }
    }
}
void trace(int s,int t) {
    while (t!=s) {
        cyc.push_back(p[t]);
        t=edge[p[t]].fi^edge[p[t]].se^t;
    }
}
void findcycle(void) {
    DSU dsu=DSU(n);
    FOR(i,1,m) if (!dsu.join(edge[i].fi,edge[i].se)) {
        int u=edge[i].fi;
        int v=edge[i].se;
        bfs(u,v,i);
        trace(u,v);
        cyc.push_back(i);
        return;
    }
}
void findtree(int id) {
    DSU dsu=DSU(n);
    REP(i,cyc.size()) if (i!=id) {
        int u=edge[cyc[i]].fi;
        int v=edge[cyc[i]].se;
        printf("%d %d\n",u,v);
        dsu.join(u,v);
    }
    FOR(i,1,m) {
        int u=edge[i].fi;
        int v=edge[i].se;
        if (dsu.join(u,v)) printf("%d %d\n",u,v);
    }
}
void process(void) {
    printf("3\n");
    REP(i,3) findtree(i);
}
int main(void) {
    loadgraph();
    findcycle();
    process();
    return 0;
}