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>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define frr(a,b,c) for (a=b;a>=c;a--)
#define maxn 100100
using namespace std;

int n,m,p[maxn],a[maxn*2],b[maxn],c[maxn],d[maxn],e[maxn],cnt,last,st[maxn];
int num[maxn],low[maxn],sm,q[maxn],f[maxn],sl[maxn],re,g[maxn];

void visit(int x,int y)
{
    int i,kt=0;
    num[x]=++cnt; low[x]=num[x]; st[++last]=x;
    fr(i,p[x]+1,p[x+1])
      if ((a[i]!=y || kt) && !d[a[i]])
      {
          if (num[a[i]]) low[x]=min(low[x],num[a[i]]);
          else
          {
              visit(a[i],x);
              low[x]=min(low[x],low[a[i]]);
          }
      }
      else
      {
          if (a[i]==y) kt=1;
      }
    if (num[x]==low[x])
    {
       sm++;
       do
       {
          i=st[last--];
          d[i]=1; e[i]=sm;
          sl[sm]++;
       } while (i!=x);
    }
}

void bfs(int x)
{
    int j=1,nq=1,i,y=e[x];
    q[1]=x; d[x]=0; g[y]=1;
    while (j<=nq)
    {
       x=q[j++];
       fr(i,p[x]+1,p[x+1])
         if (e[x]==e[a[i]])
         {
            if (d[a[i]])
            {
               d[a[i]]=0;
               q[++nq]=a[i];
               f[a[i]]=1-f[x];
            }
            else
            {
               if (f[a[i]]==f[x])
               {
                  re+=sl[y]; 
                  return;
               }
            }
         }
    }    
}

int main()
{
    int i;
    cin >> n >> m;
    fr(i,1,m)
    {
       scanf("%d%d",&b[i],&c[i]);
       p[b[i]]++; p[c[i]]++;
    }
    fr(i,2,n+1) p[i]+=p[i-1];
    fr(i,1,m)
    {
       a[p[b[i]]--]=c[i];
       a[p[c[i]]--]=b[i];
    }
    fr(i,1,n)
      if (!d[i]) visit(i,0);
    fr(i,1,n)
      if (!g[e[i]]) bfs(i);
    cout << re << endl;
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> II;

const int N = 100005;

vector<II> a[N];
int num[N], low[N];
int root[N], Size[N];
int color[N];
bool was[N], isBridge[N];
int n, nCom, m, Time;

stack<int> S;
void dfs(int u, int edgeID) {
    num[u] = ++Time; low[u] = N; S.push(u);
    for (auto it: a[u]) {
        int v = it.first;
        if (it.second == edgeID || was[v]) continue;
        if (num[v] != 0) {
            low[u] = min(low[u], num[v]);
        } else {
            dfs(v, it.second);
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] >= num[u]) {
        isBridge[edgeID] = 1;
        ++nCom;
        root[nCom] = u;
        int v;
        do {
            v = S.top(); S.pop();
            was[v] = 1;
            ++Size[nCom];
        } while (v != u);
    }
}

int Q[N]; int L, R;

bool isBipartite(int root) {
    Q[L = R = 1] = root;
    color[root] = 0;
    while (L <= R) {
        int u = Q[L++];;
        for (auto it: a[u]) {
            int v = it.first, edgeID = it.second;
            if (isBridge[edgeID]) continue;
            if (color[v] != -1) {
                if (color[v] == color[u]) return 0;
            } else {
                color[v] = color[u] ^ 1;
                Q[++R] = v;
            }
        }
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("V11TOUR.txt", "r", stdin);
#endif // ONLINE_JUDGE
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v;
        a[u].push_back(II(v, i));
        a[v].push_back(II(u, i));
    }
    for (int i = 1; i <= n; ++i)
        if (!was[i]) dfs(i, 0);
    int ans = 0;
    for (int i = 1; i <= n; ++i) color[i] = -1;
    for (int i = 1; i <= nCom; ++i)
        if (!isBipartite(root[i])) ans += Size[i];
    cout << ans << endl;
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#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,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

int n, m, low[100111], num[100111], d[100111], mark[100111], cnt, father[100111];
vector<int> ke[100111];

void dfs(int u) {
    num[u] = ++cnt; low[u] = n+1;
    REP(i,ke[u].size()) {
        int v = ke[u][i];
        if (v == father[u]) continue;
        if (!num[v]) {
            father[v] = u;
            d[v] = d[u] + 1;
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], num[v]);
    }
}

bool isBridge(int u, int v) {
    if (u != father[v] && v != father[u]) return false;
    if (v == father[u]) swap(u,v);
    if (low[v] > num[u]) return true;
    else return false;
}

void dfs2(int u) {
    mark[u] = 2;
    REP(i,ke[u].size()) {
        int v = ke[u][i];
        if (isBridge(u, v)) continue;
        if (mark[v]) continue;
        dfs2(v);
    }
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %d", &n, &m);
    FOR(i,1,m) {
        int u, v; scanf("%d %d", &u, &v);
        ke[u].PB(v);
        ke[v].PB(u);
    }

    FOR(u,1,n)
        if (!num[u]) dfs(u);

    FOR(u,1,n)
    REP(i,ke[u].size()) {
        int v = ke[u][i];
        if (v == father[u] || u == father[v]) continue;
        if ((d[u] + d[v]) % 2 == 1) continue;
        mark[u] = mark[v] = 1;
    }

    FOR(u,1,n)
        if (mark[u] == 1) dfs2(u);

    int res = 0;
    FOR(u,1,n) if (mark[u]) res++;
    cout << res;
    return 0;
}