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 happyboy99x

#include<bits/stdc++.h>
using namespace std;

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 10000, INF = 1e9, MOD = 1e9;
vector<int> g[N], rg[N];
bool vst[2][N], mod[N];
int n, m;

void enter() {
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        g[u].push_back(v);
        rg[v].push_back(u);
    }
}

void bfs(vector<int> g[], int s, bool vst[]) {
    queue<int> q; q.push(s);
    fill_n(vst, n, false); vst[s] = true;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        TR(g[u], v) if(!vst[*v])
            q.push(*v), vst[*v] = true;
    }
}

int d[N], f[N];

bool detectCycle(int u, int &timed) {
    d[u] = timed++;
    TR(g[u], v) if(vst[0][*v] && vst[1][*v])
        if(d[*v] == -1 ? detectCycle(*v, timed) : d[u] > d[*v])
            return d[u] = INF, true;
    return d[u] = INF, false;
}

void dfs(int s, int t) {
    if(f[s] != -1) return;
    f[s] = 0;
    if(s == t) f[s] = 1;
    else TR(g[s], u) if(vst[0][*u] && vst[1][*u]) {
        dfs(*u, t);
        mod[s] |= f[s] + f[*u] >= MOD || mod[*u];
        f[s] = (f[s] + f[*u]) % MOD;
    }
}

void solve() {
    bfs(g, 0, vst[0]); bfs(rg, 1, vst[1]);
    int timed = 0; fill_n(d, n, -1);
    if(!vst[0][1]) cout << 0 << '\n';
    else if(detectCycle(0, timed)) cout << "inf\n";
    else {
        fill_n(f, n, -1); dfs(0, 1);
        if(mod[0]) cout << setw(9) << setfill('0') << f[0] << '\n';
        else cout << f[0] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    solve();
    return 0;
}

Code mẫu của RR

const
  FINP='';
  FOUT='';
  MAXN=10011;
  oo=1000000000;
type
  pter=^pt;
  pt=record u:longint; link:pter; end;
var
  f1,f2:text;
  a:array[1..maxn] of pter;
  free:array[1..maxn] of boolean;
  r,d:array[1..maxn] of longint;
  c:array[1..maxn] of int64;
  ncs:array[1..maxn] of boolean;
  n:longint;
procedure inp;
var
  u,v,m,i:longint;
  last:pter;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
  read(f1,n,m);
  for i:=1 to m do
    begin
      read(f1,u,v);
      last:=a[u]; new(a[u]);
      a[u]^.u:=v; a[u]^.link:=last;
    end;
  close(f1);
end;
procedure DFS(u:longint);
var
  v:longint;
  x:pter;
begin
  free[u]:=false;
  x:=a[u];
  while x<>nil do
    begin
      v:=x^.u; x:=x^.link;
      if not free[v] then continue;
      DFS(v);
    end;
end;
procedure predone;
var
  u:longint;
  x:pter;
begin
  fillchar(free,sizeof(free),true);
  DFS(1);
  for u:=1 to n do
    if not free[u] then
      begin
        x:=a[u];
        while x<>nil do
          begin
            inc(d[x^.u]); x:=x^.link;
          end;
      end;
end;
procedure ans;
var
  i:longint;
  s:string;
begin
  str(c[2],s);
  if ncs[2] then
    for i:=1 to 9-length(s) do write(f2,0);
  writeln(f2,s);
end;
procedure solve;
var
  t,w,u,v:longint;
  x:pter;
begin
  if d[1]>0 then begin writeln(f2,'inf'); exit; end;
  t:=1; w:=1; r[1]:=1;
  c[1]:=1;
  if free[2] then begin writeln(f2,0); exit; end;
  repeat
    u:=r[t]; inc(t);
    x:=a[u];
    ncs[u]:=ncs[u] or (c[u] div oo>0);
    c[u]:=c[u] mod oo;
    if u=2 then begin ans; exit; end;
    while x<>nil do
      begin
        v:=x^.u; x:=x^.link;
        if free[v] then continue;
        c[v]:=int64(c[v])+c[u];
        ncs[v]:=ncs[v] or ncs[u];
        dec(d[v]);
        if d[v]=0 then
          begin inc(w); r[w]:=v; end;
      end;
  until t>w;
  writeln(f2,'inf');
end;
begin
  inp;
  predone;
  solve;
  close(f2);
end.

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>

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 ld PI = acos(-1.0);
const ld eps = 1e-9;
const int dr[] = { -1, 0, +1, 0};
const int dc[] = { 0, +1, 0, -1};
const int inf = (int) 1e9 + 5;
const ll linf = (ll) 1e16 + 5;
const int mod = (ll) (1e9 + eps);
#define ok puts("ok")
#define maxn 20005
#define maxe 200005

int last[maxn], last1[maxn], next[maxe], next1[maxe], adj[maxe], adj1[maxe], E = 0;
int n, m, level[maxn], que[maxn], f[maxn], d[maxn], color[maxn], danhdau[maxn];
bool flag = true;
vector<int> V;

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

int go(int u){
    int &res = f[u];
    if(res != -1) return res;
    if(level[u] < 0) return res = 0;
    if(level[u] == 0) return res = 1;
    res = 0;

    for(int e = last[u]; e != -1; e = next[e]){
        int v = adj[e];
        res += go(v);
        if(d[v]) d[u] = 1;
        if(res >= mod) {
            res -= mod;
            d[u] = 1;
        }
    }
    return res;
}

void dfs(int u){
    if(color[u]) return;
    color[u] = 1;
    for(int e = last[u]; e != -1; e = next[e]){
        int v = adj[e];
        dfs(v);
    }
    V.pb(u);
}

void dfs1(int u){
    if(danhdau[u]) return;
    danhdau[u] = 1;
    for(int e = last1[u]; e != -1; e = next1[e]){
        int v = adj1[e];
        if(!danhdau[v] && level[v] != -1 && color[v]){
            flag = false;
        }
    }
}

int main(){
//  freopen("in.txt", "r", stdin);
    scanf("%d %d", &n, &m);
    int u, v;
    ms(last, -1); ms(last1, -1); E = 0; ms(level, -1); ms(color, 0); ms(danhdau, 0);
    Rep(run, m){
        scanf("%d %d", &u, &v);
        add(u, v);
    }
    level[2] = 0;
    int size = 0; que[size++] = 2;
    Rep(i, size){
        u = que[i];
        for(int e = last1[u]; e != -1; e = next1[e]){
            v = adj1[e];
            if(level[v] == -1){
                level[v] = level[u] + 1;
                que[size++] = v;
            }
        }
    }

    dfs(1);

    for(int i = sz(V) - 1; i >= 0; i--) if(!danhdau[V[i]]){
        dfs1(V[i]);
    }

    if(!flag){
        cout << "inf" << endl;
        return 0;
    }

    ms(f, -1); ms(d, 0);
    int res = go(1);
    if(d[1]) printf("%09d", res);
    else printf("%d", res);
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

typedef vector<int> VI;
typedef unsigned int uint;

#define maxn 10010
#define pb push_back
#define mod 1000000000

int n;
VI ke[maxn], ken[maxn];
int dist[maxn], f[maxn];
bool inq[maxn], larger[maxn], dt[maxn], vs[maxn];
queue<int> q;

void tinh(int i) {
    if(i==2) {
        f[i] = 1;
        larger[i] = false;
        return;
    }
    if(dt[i]) return;
    dt[i] = true;
    f[i] = 0;
    larger[i] = false;
    for(uint k=0;k<ke[i].size();++k) {
        int j = ke[i][k];
        tinh(j);
        f[i] += f[j];
        larger[i] |= larger[j];
        if(f[i]>=mod) {
            f[i] -= mod;
            larger[i] = true;
        }
    }
}

int main() {
    int u, v, m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i) {
        scanf("%d%d",&u,&v);
        ke[u].pb(v);
        ken[v].pb(u);
    }

    vs[1] = true;
    q.push(1);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(uint k=0;k<ke[u].size();++k) {
            int v = ke[u][k];
            if(!vs[v]) {
                vs[v] = true;
                q.push(v);
            }
        }
    }

    if(!vs[2]) {
        puts("0");
        return 0;
    }

    q.push(2);
    dist[2] = 0;
    inq[2] = true;
    bool vc = false;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        if(dist[u]>n) {
            vc = true;
            break;
        }
        for(uint k=0;k<ken[u].size();++k) {
            int v = ken[u][k];
            if(dist[v]<dist[u]+1 && vs[v]) {
                dist[v] = dist[u]+1;
                if(!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
    if(vc) puts("inf");
    else {
        tinh(1);
        if(larger[1]) printf("%09d",f[1]);
        else printf("%d",f[1]);
    }
    //system("pause");
    return 0;
}