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

//no 3 vertex - cycle => DAG
//if A -> B, B -> C then A -> C => Transitive Closure 
//=> Maximum Independent Set == Minimum Path Cover
#include <bits/stdc++.h>
const int N = 1010;
using namespace std;
int matchX[N], matchY[N], T[N], Q[N];
vector<int> a[N];
int n, m;

int BFS() {
    int l = 1, r = 0;
    for(int i = 1; i <= n; i++)
        if (matchX[i] == 0) Q[++r] = i;
    for(int i = 1; i <= n; i++) T[i] = 0;
    while (l <= r) {
        int u = Q[l++];
        for(int i = 0; i < a[u].size(); i++) {
            int v = a[u][i];
            if (T[v] == 0) {
                T[v] = u;
                if (matchY[v] == 0) return v;
                Q[++r] = matchY[v];
            }
        }
    }
    return 0;
}

void Enlarge(int y) {
    int x, next;
    for(; y; y = next) {
        x = T[y];
        next = matchX[x];
        matchX[x] = y;
        matchY[y] = x;
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int i, u, v;
    for(i = 1; i <= m; i++) {
        cin >> u >> v;
        a[u].push_back(v);
    }
    int res = 0;
    while (i = BFS()) Enlarge(i);
    for(int i = 1; i <= n; i++)
        if (matchX[i] == 0) res++;
    cout << res << endl;
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=1001;
var
  a:array[1..MAXN,1..MAXN] of longint;
  queue,trace,matchX,matchY,deg:array[1..MAXN] of longint;
  m,kq,n:longint;
  f1,f2:text;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i,u,v:longint;
begin
  read(f1,n,m);
  for i:=1 to m do
    begin
      read(f1,u,v);
      inc(deg[u]); a[u,deg[u]]:=v;
    end;
end;
procedure ans;
var
  i,count:longint;
begin
  count:=0;
  for i:=1 to n do
    if matchX[i]<>0 then inc(count);
  writeln(f2,n-count);
end;
function findPath(start:longint):longint;
var
  first,last,i,v,u:longint;
begin
  first:=1; last:=1; queue[1]:=start;
  while first<=last do
    begin
      u:=queue[first]; inc(first);
      for i:=1 to deg[u] do
        begin
          v:=a[u,i];
          if (trace[v]=0) and (matchX[u]<>v) then
            begin
              trace[v]:=u;
              if matchY[v]=0 then exit(v);
              inc(last); queue[last]:=matchY[v];
            end;
        end;
    end;
  exit(0);
end;
procedure enlarge(y:longint);
var
  x,next:longint;
begin
  repeat
    x:=trace[y];
    next:=matchX[x];
    matchX[x]:=y;
    matchY[y]:=x;
    y:=next;
  until y=0;
end;
procedure solve;
var
  x,y:longint;
begin
  for x:=1 to n do
    begin
      fillchar(trace,sizeof(trace),0);
      y:=findPath(x);
      if y<>0 then enlarge(y);
    end;
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

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

#define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(__typeof(a) 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))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

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> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
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> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
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 = 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;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {0, 0, -1, +1};
const int dc[] = {-1, +1, 0, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = ld(1e-9);
const ll mod = 100000007;
typedef pair<int, int> II;
// Dinic

#define maxn 1011
#define maxe 150111

struct HopcroftKarp{
    int nx, ny, E, adj[maxe], next[maxe], last[maxn],
    matx[maxn], maty[maxn], que[maxn], level[maxn], run[maxn];

    void init(int _nx, int _ny){
        nx = _nx; ny = _ny; E = 0;
        For(i, 1, nx) matx[i] = -1, last[i] = -1;
        For(i, 1, ny) maty[i] = -1;
    }  

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

    bool bfs(){
        bool found = false;
        int size = 0;
        For(x, 1, nx){
            if(matx[x] != -1) level[x] = -1;
            else{
                level[x] = 0;
                que[size++] = x;
            }
        }
        Rep(i, size){
            for(int x = que[i], e = last[x]; e != -1; e = next[e]){
                int y = adj[e];
                if(maty[y] == -1) found = true;
                else if(level[maty[y]] == -1){
                    level[maty[y]] = level[x] + 1;
                    que[size++] = maty[y];
                }
            }
        }

        return found;
    }

    int dfs(int x){
        for(int &e = run[x]; e != -1; e = next[e]){
            int y = adj[e];
            if(maty[y] == -1 || ( level[maty[y]] == level[x] + 1 && dfs(maty[y]))){
                maty[y] = x;
                matx[x] = y;
                return 1;
            }
        } 
        return 0;
    }

    int maxMatching(){
        int total = 0;
        while(bfs()){
            For(x, 1, nx) run[x] = last[x];
            For(x, 1, nx) if(matx[x] == -1) total += dfs(x);
        }
        return total;
    }

} hopkarp;

int adj[maxn * maxn / 2], next[maxn * maxn / 2], last[maxn], E;

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

void go(int x){
    bool flag[maxn] = {0};
    int que[maxn], size = 0, u, v;
    que[size++] = x;
    flag[x] = 1;
    Rep(i, size){
        u = que[i];
        for(int e = last[u]; e != -1; e = next[e]){
            v = adj[e];
            if(!flag[v]){
                hopkarp.add(x, v);
                flag[v] = 1;
                que[size++] = v;
            }
        }
    }
}

int main(){
   // OPEN();
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int n, m, x, y;
    scanf("%d %d",&n, &m);
    E = 0; ms(last, -1);
    hopkarp.init(n, n);
    Rep(run, m){
        scanf("%d %d", &x, &y);
        add(x, y);
      // hopkarp.add(x, y);
    }

    For(i, 1, n){
        go(i);
    }
    printf("%d\n", n - hopkarp.maxMatching());
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int n, m;
int a[1010][1010];
bool vs[1010];
int x[1010], y[1010];

bool dfs(int i) {
    if(vs[i]) return false;
    vs[i] = true;
    for(int j=1;j<=n;++j) if(a[i][j]) {
        if(y[j]==0 || dfs(y[j])) {
            x[i] = j;
            y[j] = i;
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        a[u][v] = true;
    }
    int res = n;
    for(int i=1;i<=n;++i) {
        memset( vs, 0, sizeof(vs));
        if(dfs(i)) --res;
    }
    cout << res << endl;
    return 0;
}