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='';
      fo='';
      maxn=300;
var n,num,dem,sm:longint;
    a:array[1..maxn,1..maxn] of longint;
    d,e,q,re:array[1..maxn] of longint;
    kt:boolean;

procedure rf;
var x,y:longint;
begin
     assign(input,fi); reset(input);
     readln(n);
     while not eof do
     begin
          readln(x,y);
          a[x,y]:=1; a[y,x]:=1;
     end;
     for x:=1 to n do d[x]:=-1;
     close(input);
end;

procedure bfs(x:longint);
var i,j,t:longint;
begin
     num:=1; i:=1; q[1]:=x; d[x]:=0; inc(sm); e[x]:=sm;
     repeat
           for j:=1 to n do
               if a[q[i],j]=1 then
               begin
                    if d[j]=-1 then
                    begin
                         inc(num); q[num]:=j; d[j]:=(d[q[i]]+1) and 1;
                         e[j]:=sm;
                    end
                    else
                    begin
                         if d[j]=d[q[i]] then
                         begin
                              kt:=true;
                              exit;
                         end;
                    end;
               end;
           inc(i);
     until i>num;
     j:=0;
     for i:=1 to num do
         if d[q[i]]=0 then inc(j);
     if j>=num-j then t:=0 else t:=1;
     for i:=1 to num do
         if d[q[i]]=t then
         begin
              inc(dem);
              re[dem]:=q[i];
         end;
end;

procedure pr;
var i,j:longint;
begin
     kt:=false; dem:=0; sm:=0;
     for i:=1 to n do
     begin
          if d[i]=-1 then bfs(i);
          if kt then exit;
     end;
end;

procedure wf;
var t,i,j:longint;
begin
     assign(output,fo); rewrite(output);
     if kt then write('YES')
     else
     begin
          for i:=1 to dem-1 do
              for j:=i+1 to dem do
                  if re[i]>re[j] then
                  begin
                       t:=re[i]; re[i]:=re[j]; re[j]:=t;
                  end;
          writeln('NO');
          writeln(dem);
          for i:=1 to dem do write(re[i],' ');
     end;
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

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>
#include <climits>
#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 TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#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 = 666;

using namespace std;

VI a[N], half[2];
int side[N];
bool visit[N][N][2];
bool YES, foundPath;
int n;

void readInput() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int u, v;
    while (cin >> u >> v) {
        a[u].PB(v); a[v].PB(u);
    }
}

void buildConnectedPairs() {
    REP(source, 1, n) {
        queue<II> Q;
        REP(i, 1, n)
            visit[source][i][0] = visit[source][i][1] = 0;
        visit[source][source][0] = 1;
        Q.push(MP(source, 0));
        while (!Q.empty()) {
            II uu = Q.front(); Q.pop();
            int u = uu.X, parity = uu.Y ^ 1;
            TR(v, a[u]) if (!visit[source][*v][parity]) {
                visit[source][*v][parity] = 1;
                Q.push(MP(*v, parity));
            }
        }
    }
    REP(i, 1, n) REP(j, i + 1, n)
        if (visit[i][j][0] && visit[i][j][1]) {
            YES = 1; break;
        }
}

void dfsColor(int u, int c) {
    side[u] = c;
    TR(v, a[u]) if (side[*v] == -1)
        dfsColor(*v, c ^ 1);
}

void buildBipartiteGraph() {
    RESET(side, -1);
    REP(i, 1, n) if (side[i] == -1) dfsColor(i, 0);
    REP(i, 1, n) half[side[i]].PB(i);
    REP(i, 1, n) a[i].clear();
    TR(u, half[0]) TR(v, half[1])
    if (visit[*u][*v][1]) a[*u].PB(*v);
}

bool was[N];
int matchX[N], matchY[N];
int matched;

void dfsMatch(int u) {
    TR(v, a[u]) if (!was[*v]) {
        was[*v] = 1;
        if (matchY[*v] == 0) foundPath = 1;
        else dfsMatch(*v);
        if (foundPath) {
            matchY[*v] = u;
            return;
        }
    }
}

void maximumMatching() {
    int lst[N], nLst = 0;
    TR(u, half[0]) lst[nLst++] = *u;
    bool stop;
    do {
        stop = 1;
        TR(u, half[1]) was[*u] = 0;
        REPD(i, nLst - 1, 0) {
            foundPath = 0;
            dfsMatch(lst[i]);
            if (foundPath) {
                lst[i] = lst[--nLst];
                stop = 0;
                matched++;
            }
        }
    } while (!stop);
}

void maximumIndependentSet() {
    queue<int> Q;
    bool pushed[N]; RESET(pushed, 0);
    TR(u, half[1])
    if (matchY[*u])
        matchX[matchY[*u]] = *u;
    TR(u, half[0])
    if (matchX[*u] == 0) {
        Q.push(*u);
        pushed[*u] = 1;
    }
    bool inZX[N], inZY[N];
    RESET(inZX, 0); RESET(inZY, 0);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        inZX[u] = 1;
        TR(v, a[u]) {
            inZY[*v] = 1;
            if (matchY[*v] && !pushed[matchY[*v]]) {
                pushed[matchY[*v]] = 1;
                Q.push(matchY[*v]);
            }
        }
    }
    cout << "NO\n" << n - matched << endl;
    VI ans;
    TR(u, half[0]) if (inZX[*u]) ans.PB(*u);
    TR(u, half[1]) if (!inZY[*u]) ans.PB(*u);
    sort(ALL(ans));
    TR(u, ans) cout << *u << ' ';
}

void solve() {
    buildBipartiteGraph();
    maximumMatching();
    maximumIndependentSet();
}

int main() {
    readInput();
    buildConnectedPairs();
    if (YES) cout << "YES\n";
    else solve();
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define REP(i,a) for(int i=0, _a=(a); i<_a; i++)
#define MAXN 311
#define PB push_back
using namespace std;

int n;
vector<int> ke[MAXN];

void inp() {
    scanf("%d", &n);
    int u, v;
    while (scanf("%d %d", &u, &v) == 2) {
        ke[u].PB(v);
        ke[v].PB(u);
    }
}

int canGo[MAXN][MAXN][2], visited[MAXN][2], qu[MAXN*2], qt[MAXN*2], front, rear;

void push(int u, int t) {
    if (visited[u][t]) return ;
    visited[u][t] = 1;
    rear++;
    qu[rear] = u;
    qt[rear] = t;
}

void pop(int& u, int& t) {
    u = qu[front];
    t = qt[front];
    front++;
}

void bfs(int u, int t) {
    memset(visited, 0, sizeof visited);
    front = 1; rear = 0;
    push(u,t);
    while (front <= rear) {
        pop(u,t);
        REP(iv, ke[u].size()) {
            int v = ke[u][iv];
            push(v,1-t);
        }
    }
}

void init() {
    FOR(i,1,n) {
        bfs(i,0);
        FOR(j,1,n)
        FOR(t,0,1)
            canGo[i][j][t] = visited[j][t];
    }
}

int dd[2][MAXN], choose[MAXN], cnt[2];

void dfs(int u, int t, int now, int get) {
    dd[now][u] = 1;
    if (get && !t) choose[u] = 1;
    cnt[t]++;
    REP(iv, ke[u].size()) {
        int v = ke[u][iv];
        if (!dd[now][v])
            dfs(v, 1-t, now, get);
    }
}

void solve() {
    FOR(i,1,n)
    FOR(j,i+1,n)
        if (canGo[i][j][0] && canGo[i][j][1]) {
            printf("YES");
            return ;
        }
    int res = 0;
    FOR(i,1,n)
    if (!dd[0][i]) {
        cnt[0] = cnt[1] = 0;
        dfs(i, 0, 0, false);
        res += max(cnt[0], cnt[1]);
        if (cnt[0] > cnt[1]) dfs(i, 0, 1, true);
        else dfs(i, 1, 1, true);
    }
    printf("NO\n");
    printf("%d\n", res);
    FOR(i,1,n)
    if (choose[i])
        printf("%d ", i);
}

int main() {
    inp();
    init();
    solve();
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
    if (rsz <= 0) {
        ptr = 0;
        rsz = (int) fread(bf, 1, bfsz, stdin);
        if (rsz <= 0)
            return EOF;
    }
    --rsz;
    return bf[ptr++];
}
void ga(char &c) {
    c = EOF;
    while (!isalpha(c))
        c = gc();
}
int gs(char s[]) {
    int l = 0;
    char c = gc();
    while (isspace(c))
        c = gc();
    while (c != EOF && !isspace(c)) {
        s[l++] = c;
        c = gc();
    }
    s[l] = '\0';
    return l;
}
template<class T> bool gi(T &v) {
    v = 0;
    char c = gc();
    while (c != EOF && c != '-' && !isdigit(c))
        c = gc();
    if (c == EOF)
        return false;
    bool neg = c == '-';
    if (neg)
        c = gc();
    while (isdigit(c)) {
        v = v * 10 + c - '0';
        c = gc();
    }
    if (neg)
        v = -v;
    return true;
}

typedef pair<int, int> II;

const double PI = acos(-1.0);
const double eps = 1e-12;

const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ll mod = (ll)1e9 + 7;

#define maxn 305
#define maxe 200005

int n;
int adj[maxe], last[maxn], next[maxe], E = 0;
int f[maxn][2];
II que[maxe];
vector<int> res;
bool check = false;

void add(int u, int v){
    adj[E] = v; next[E] = last[u]; last[u] = E++;
    adj[E] = u; next[E] = last[v]; last[v] = E++;
}

void bfs(int id){
    int size = 0;
    que[size++] = mp(id, 0);
    f[id][0] = 1;
    int u, t, v;
    Rep(i, size){
        u = que[i].fi; t = que[i].se;
        for(int e = last[u]; e != -1; e = next[e]){
            v = adj[e];
            if(!f[v][1 - t]){
                f[v][1 - t] = 1;
                que[size++] = mp(v, 1 - t);
            }
        }
    }

    int odd = 0, even = 0;
    if(f[id][1]) {
        check = true;
        return;
    }

    Rep(i, size){
        if(que[i].se) odd++;
        else even++;
    }

    Rep(i, size){
        if(even >= odd && que[i].se == 0) res.pb(que[i].fi);
        if(even < odd && que[i].se == 1) res.pb(que[i].fi);
    }
}

int main(){
//  freopen("in.txt", "r", stdin);

    ms(f, 0); ms(last, -1);

    scanf("%d", &n);
    int u, v;
    while(scanf("%d %d", &u, &v) > 0){
        add(u, v);
    }

    For(i, 1, n) if(!f[i][0] && !f[i][1]){
        bfs(i);
        if(check) break;
    }

    if(check){
        cout << "YES" << endl;
        return 0;
    }

    sort(all(res));
    cout << "NO" << endl;
    cout << sz(res) << endl;
    Rep(i, sz(res)) cout << res[i] << " ";

    return 0;
}

Code mẫu của khuc_tuan

//{$APPTYPE CONSOLE}
 {$MODE DELPHI}

uses
    SysUtils, Math;

type
    TArr1 = array[0..1000] of integer;

var
    a : array[0..1000,0..1000] of boolean;
    khuyen, cl : boolean;
    color, c2 : TArr1;
    d1, d2 : integer;
    n, i, u, v, res : integer;

procedure dfs(i : integer; var c : TArr1);
var
    j : integer;
begin
    if c[i] = 1 then inc(d1)
    else inc(d2);
    for j:=1 to n do
        if a[i,j] then
            if c[j] = 0 then
            begin
                c[j] := 3 - c[i];
                dfs(j, c);
            end
            else if c[j] = c[i] then
            begin
                if i=j then
                    khuyen := true
                else
                    cl := true;
            end;
end;

begin
    readln(n);
    while not eof do
    begin
        readln(u,v);
        // if u = v then continue;
        a[u,v] := true;
        a[v,u] := true;
    end;
    res := 0;
    for i:=1 to n do
        if color[i]=0 then
        begin
            color[i] := 1;
            d1 := 0;
            d2 := 0;
            khuyen := false;
            dfs(i, color);
            if khuyen and (d1 + d2 > 1) then
                cl := true;
            if d1 < d2 then c2[i] := 2
            else c2[i] := 1;
            res := res + max( d1, d2);
            dfs(i, c2);
        end;
    if cl then writeln('YES')
    else
    begin
        writeln('NO');
        writeln(res);
        for i:=1 to n do
            if c2[i] = 1 then
                write(i, ' ');
    end;
end.