Đề bài:

• http://vn.spoj.com/problems/STABLE/

Thuật toán:

• BFS từ đỉnh S
• Gọi bac[i] là đồ dài đường đi ngắn nhất từ s đến i
  • bac[i] = bac[j] + 1
  • với i kề j và j duyệt BFS trước i
• ok[i] = 1 nếu i ổn định, ok[i] = 0 nếu i không ổn định.
• Hãy tham khảo code để biết cách kiểm tra xem i có ổn định không

Code:

• Pascal: http://ideone.com/BGjZip
• C++: http://ideone.com/AQF1wp

#include 
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;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()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E4+3;
const int oo = 1e9+3;

int n, m, s, u, v, res, bac[MAXN],adj[MAXN][MAXN];
bool ok[MAXN];
queue q;
vector a[MAXN];

int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    cin >> n >> m >> s;
    FOR(i,1,m) {
        cin >> u >> v;
        if (!adj[u][v])
            a[u].push_back(v);
        adj[u][v] = 1;
    }
    q.push(s); bac[s] = 1;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        for(int i=0; i
const
  fi='stable.inp';
  fo='stable.out';
  maxn=10000;
  maxm=50000;
var
  link,head,ke : array[1..maxm] of longint;
  i,j,n,m,st,ans,s,dau,cuoi,u,v : longint;
  q,bac : array[1..maxn] of longint;
  ok : array[1..maxn] of boolean;
  a : array[1..maxn,1..maxn] of boolean;
procedure push(x : longint);
  begin
    inc(cuoi);
    q[cuoi] := x;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
begin
//  assign(input,fi);reset(input);
//  assign(output,fo);rewrite(output);
  read(n,m,s);
  for i := 1 to m do
    begin
      read(u,v);
      if a[u,v] = false then
      add(i,u,v);
      a[u,v] := true;
    end;
  dau := 1; cuoi := 0;
  push(s);
  bac[s] := 1;
  while (dau <= cuoi) do
    begin
      u := q[dau];
      inc(dau);
      i := head[u];
      while i <> 0 do
        begin
          v := ke[i];
          if bac[v] = 0 then
            begin
              if ok[u] then ok[v] := true;
              bac[v] := bac[u] + 1;
              push(v);
            end
            else
          if bac[v] = bac[u] + 1 then
            begin
              ok[v] := true;
            end;
          i := link[i];
        end;
    end;
  for i := 1 to n do
    if ok[i] then inc(ans);
  writeln(ans);
//  close(input);close(output);
end.