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 <cstring>
#include <vector>
#include <queue>
using namespace std;

int n, S, T, onPath[10010], prev[10010], flag[10010], mark[10010];
vector <int> a[10010], path;

int bfs()
{
    queue <int> q;
    prev[S] = -1; q.push(S);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = 0; i < int(a[x].size()); i++)
        {
            int y = a[x][i];
            if (!prev[y]) q.push(y), prev[y] = x;
        }
    }

    if (!prev[T]) return 0;

    int x = T;
    path.push_back(T);
    while (x != S) x = prev[x], path.push_back(x);

    path.push_back(0);
    reverse(path.begin(), path.end());
    for (int i = 1; i < int(path.size()); i++) onPath[path[i]] = i;

    return 1;
}

int findFurthestOnPath(int x, int z)
{
    if (onPath[x] && onPath[x] != z) return onPath[x];
    flag[x] = z;
    int res = 0;
    for (int i = 0; i < int(a[x].size()); i++)
    {
        int y = a[x][i];
        if (flag[y] != z) res = max(res, findFurthestOnPath(y, z));
    }
    return res;
}

int main()
{
    int m, x, y;
    cin >> n >> m >> S >> T;
    while (m--) scanf("%d%d", &x, &y), a[x].push_back(y); 

    if (!bfs()) 
    {
        puts("0");
        return 0;
    }

    for (int i = 1; i < int(path.size()); i++)
    {
        int j = findFurthestOnPath(path[i], i);
        if (i + 1 < j) mark[i + 1]++, mark[j]--;
    }

    int ans = 0;
    for (int i = 2; i + 1 < int(path.size()); i++)
    {
        mark[i] += mark[i - 1];
        ans += !mark[i];
    }

    cout << ans << endl;
}

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 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 = 10005;
const int M = 100005;
using namespace std;
VI super[N], adj[N], a[N];
int num[N], low[N], f[N], lab[N], T[N];
bool was[N], deleted[M];
int n, m, s, t, timer, scc;

void readInput() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> s >> t;
    int u, v;
    FOR(i, 0, m) {
        cin >> u >> v;
        a[u].PB(v);
    }
}
void bfsFindPath() {
    queue<int> Q;
    Q.push(s); T[s] = -1;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        TR(it, a[u]) if (T[*it] == 0) {
            T[*it] = u;
            if (*it == t) return;
            Q.push(*it);
        }
    }
}

VI path;
bool inPath[N];
int id[N];
void buildPath() {
    for(int v = t; v != s; v = T[v]) path.PB(v);
    path.PB(s);
    reverse(ALL(path));
    FOR(i, 0, SZ(path))
        inPath[path[i]] = 1, id[path[i]] = i;
}

stack<int> S;
void dfsTarjan(int u) {
    num[u] = low[u] = ++timer; S.push(u);
    TR(it, a[u]) {
        int v = *it;
        if (was[v] || inPath[v]) continue;
        if (num[v]) low[u] = min(low[u], num[v]);
        else {
            dfsTarjan(v);
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] >= num[u]) {
        int v;
        do {
            v = S.top(); S.pop();
            was[v] = 1;
            lab[v] = scc;
            super[scc].PB(v);
        } while (v != u);
        scc++;
    }
}

void buildDAG() {
    REP(i, 1, n)
    if (!was[i]) dfsTarjan(i);
    FOR(i, 0, scc)
        TR(u, super[i]) TR(it, a[*u])
        if (!inPath[*it])
            adj[i].PB(lab[*it]);
}

void dpOnDAG() {
    FOR(i, 0, scc) {
        TR(u, super[i]) TR(it, a[*u])
        if (inPath[*it]) f[i] = max(f[i], id[*it]);

        TR(u, adj[i])
            f[i] = max(f[i], f[*u]);
    }
}

int in[N], out[N];
void solve() {
    FOR(i, 0, SZ(path)) {
        int right = f[lab[path[i]]] - 1;
        if (right > i) {
            in[i + 1]++;
            out[right]++;
        }
    }
    int cnt = 0, ans = SZ(path) - 2;
    FOR(i, 0, SZ(path)) {
        cnt += in[i];
        if (cnt) ans--;
        cnt -= out[i];
    }
    cout << ans;
}

int main() {
    readInput();
    bfsFindPath();
    buildPath();
    buildDAG();
    dpOnDAG();
    solve();
    return 0;
}

Code mẫu của RR

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

#define MAXN 10111
#define FOR(i,a,b)  for(long i=a; i<=b; i++)
#define FORD(i,a,b) for(long i=a; i>=b; i--)
#define FORV(i,v)   for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define V vector<long>
#define PB push_back
using namespace std;

long n,m,s,t,k,queue[MAXN],trace[MAXN],next[MAXN],x[MAXN],lab[MAXN],f[MAXN];
V ke[MAXN];

void inp() {
    scanf("%ld %ld %ld %ld",&n,&m,&s,&t);
    FOR(i,1,m) {
        long u,v;
        scanf("%ld %ld",&u,&v);
        ke[u].PB(v);
    }
}

void bfs() {
    long first=1,last=1; queue[1]=s;
    while (first<=last) {
        long u=queue[first++];
        FORV(v,ke[u])
        if (!trace[*v]) {
            trace[*v]=u;
            if (*v==t) return ;
            queue[++last]=*v;
        }
    }
}

void dfs(long u) {
    FORV(v,ke[u])
        if (lab[*v]) f[u]=max(f[u],lab[*v]);
        else {
            if (f[*v]) f[u]=max(f[u],f[*v]);
            else {
                dfs(*v);
                f[u]=max(f[u],f[*v]);
            }
        }
}

void solve() {
    trace[s]=s;
    bfs();
    if (!trace[t]) {
        printf("0\n");
        return ;
    }
    long v=t;

    while (v!=s) {
        long u=trace[v];
        next[u]=v;
        v=u;
    }

    long u=s; long k=0;
    while (u!=t) {
        long v=next[u];
        x[++k]=u; lab[u]=k;
        u=v;
    }
    x[++k]=t; lab[t]=k;

    FOR(i,1,k) dfs(x[i]);

    long res=0,ln=f[x[1]];
    FOR(i,2,k-1) {
        if (lab[x[i]]>=ln) res++;
        ln=max(ln,f[x[i]]);
    }
    printf("%ld",res);
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    inp();
    solve();
    return 0;
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <cstring>
#define maxn 100005
using namespace std;

bool mark[maxn],next[maxn];
int d[maxn],trace[maxn];
vector<int> adj[maxn];
int n,m,s,t;

void BFS(int start) {
  memset(d,-1,sizeof(d));
  d[start] = 0;
  deque<int> q;
  q.push_back(start);

  while (!q.empty()) {
    int u = q.front();
    q.pop_front();
    for (int i = 0; i < adj[u].size(); i++) {
      int v = adj[u][i];
      if (d[v] < 0 || d[v] > d[u] + mark[v]) {
        d[v] = d[u] + mark[v];
    trace[v] = u;
    if (mark[v]) q.push_back(v); else q.push_front(v);
      }
    }
  }
  if (d[t] < 0) d[t] = 0;
}

void track(int u) {
  next[u] = true;
  if (u == s) return;
  track(trace[u]);
}

void printAnswer() {
  vector<int> answer;
  for (int i = 1; i <= n; i++)
    if (i != s && i != t && mark[i]) answer.push_back(i);
  printf("%d\n", answer.size());
//  for (int i = 0; i < answer.size(); i++) printf("%d ", answer[i]);
}

int main() {
//  freopen("assassination.in","r",stdin);
  scanf("%d %d %d %d", &n, &m, &s, &t);
  for (int i = 0; i < m; i++) {
    int x,y;
    scanf("%d %d", &x, &y);
    adj[x].push_back(y);
  }
  memset(mark,true,sizeof(mark));
  while (1) {
    int temp = d[t];
    BFS(s);
    if (d[t] == temp) break;
    memset(next,false,sizeof(next));
    track(t);
    for (int i = 1; i <= n; i++) mark[i] &= next[i];
  }
  printAnswer();
}

Code mẫu của skyvn97

#ifndef graph_h
#define graph_h

int calculate(int N, int M, int S, int T, int U[], int V[]);

#endif

#include<bits/stdc++.h>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
using namespace std;
class SegmentTree {
private:
    int n;
    vector<bool> lazy;
    void update(int i,int l,int r,int u,int v) {
        if (l>v || r<u || l>r || v<u) return;
        if (u<=l && r<=v) {
            lazy[i]=true;
            return;
        }
        int m=(l+r)>>1;
        update(2*i,l,m,u,v);
        update(2*i+1,m+1,r,u,v);
    }
public:
    SegmentTree() {
        n=0;
    }
    SegmentTree(int n) {
        this->n=n;
        lazy.assign(4*n+7,false);
    }
    void update(int l,int r) {
        update(1,1,n,l,r);
    }
    bool get(int x) const {
        int i=1;
        int l=1;
        int r=n;
        while (true) {
            if (lazy[i]) return (true);
            if (l==r) return (false);
            int m=(l+r)>>1;
            if (x>m) {
                i=2*i+1;
                l=m+1;
            } else {
                i=2*i;
                r=m;
            }
        }
    }
};
vector<int> adj[MAX];
vector<int> path;
int trace[MAX];
int pathPos[MAX];
int n,m,s,t,nComp,cnt;
int low[MAX],num[MAX],compID[MAX];
vector<int> comp[MAX];
stack<int> st;
int storedMaxNode[MAX];
bool bfs(void) {
    memset(trace,-1,sizeof trace);
    queue<int> q;
    trace[s]=0;
    q.push(s);
    while (!q.empty()) {
        int u=q.front();q.pop();
        FORE(it,adj[u]) if (trace[*it]<0) {
            int v=*it;
            trace[v]=u;
            q.push(v);
        }
    }
    return (trace[t]>0);
}
void findPath(void) {
    memset(pathPos,-1,sizeof pathPos);
    for (int u=t;u!=s;u=trace[u]) path.push_back(u);
    path.push_back(s);
    reverse(ALL(path));
    REP(i,path.size()) pathPos[path[i]]=i;
}
void dfs(int u) {
    low[u]=num[u]=++cnt;
    st.push(u);
    FORE(it,adj[u]) if (pathPos[*it]<0 && compID[*it]==0) {
        int v=*it;
        if (num[v]==0) {
            dfs(v);
            low[u]=min(low[u],low[v]);
        } else low[u]=min(low[u],num[v]);
    }
    if (low[u]==num[u]) {
        nComp++;
        int v;
        do {
            v=st.top();st.pop();
            compID[v]=nComp;
            comp[nComp].push_back(v);
        } while (v!=u);
    }
}
void tarjan(void) {
    FOR(i,1,n) if (pathPos[i]<0 && num[i]==0) dfs(i);
    memset(storedMaxNode,-0x3f,sizeof storedMaxNode);
}
int maxNode(int u) {
    if (storedMaxNode[u]>=-1) return (storedMaxNode[u]);
    int &res=storedMaxNode[u];
    res=-1;
    FORE(it,comp[u]) FORE(jt,adj[*it]) {
        if (pathPos[*jt]>=0) res=max(res,pathPos[*jt]);
        else if (compID[*jt]!=u) res=max(res,maxNode(compID[*jt]));
    }
    return (res);
}
int maxPathNode(int u) {
    int res=-1;
    FORE(it,adj[u]) if (pathPos[*it]<0) res=max(res,maxNode(compID[*it]));
    return (res);
}
int process(void) {
    SegmentTree myit((int)path.size()-2);
    REP(i,path.size()) {
        int j=maxPathNode(path[i]);
        if (i+1<=j-1) myit.update(i+1,j-1);
        //printf("From %d to %d\n",i,j);
    }
    int res=0;
    FOR(i,1,(int)path.size()-2) if (!myit.get(i)) res++;
    return (res);
}
int calculate(int N, int M, int S, int T, int U[], int V[]) {
    n=N;m=M;s=S+1;t=T+1;
    if (s==t) return (0);
    REP(i,m) {
        int u=U[i]+1;
        int v=V[i]+1;
        adj[u].push_back(v);
        if (u==s && v==t) return (0);
    }
    if (!bfs()) return (0);
    findPath();
    //REP(i,path.size()) printf("%d ",path[i]); printf("\n");
    tarjan();
    /*FOR(i,1,nComp) {
        printf("Comp #%d:",i);
        FORE(it,comp[i]) printf(" %d",*it);
        printf("\n");
    }*/
    return (process());
}

#include <stdio.h>

int main() {
    //freopen("graph.in","r",stdin);
    //freopen("graph.out","w",stdout);

    int N,M,S,T; scanf("%d%d%d%d",&N,&M,&S,&T);
    S--;T--;
    int *U = new int[M];
    int *V = new int[M];

    for (int i = 0; i < M; i++) {
        scanf("%d%d",&U[i],&V[i]);
        U[i]--;V[i]--;
    }

    printf("%d\n",calculate(N,M,S,T,U,V));

    return 0;
}

Code mẫu của khuc_tuan

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

int n, m, s, t, comp;
vector<int> ke[10010 * 2], ds;
int vs[10010 * 2], cant[10010 * 2];

bool dfs(int i) {
    if(i==t+n) return true;
    if(vs[i]) return false;
    vs[i] = true;
    for(int k=0;k<ke[i].size();++k) {
        int j = ke[i][k];
        if(dfs(j)) {
            if(i+n==j) cant[i] = j;
            ke[j].push_back(i);
            ds.push_back(i);
            return true;
        }       
    }
    return false;
}

void dfs2(int i) {
    vs[i] = comp;
    for(int k=0;k<ke[i].size();++k)
        if(!vs[ke[i][k]] && ke[i][k]!=cant[i]) dfs2(ke[i][k]);
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i=0;i<m;++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        ke[u+n].push_back(v);
    }
    for(int i=1;i<=n;++i) ke[i].push_back(i+n);
    dfs(s);
    memset( vs, 0, sizeof(vs));
    for(int k=ds.size()-1;k>=0;--k) if(!vs[ds[k]]) {
        ++comp;
        dfs2(ds[k]);
    }
    int dem = 0;
    for(int i=1;i<=n;++i) if(i!=s && i!=t && vs[i] != vs[i+n]) ++dem;
    printf("%d\n", dem);
    return 0;
}