## Editorial for VOI 10 Bài 2 - Ổn định

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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 oo=100000000;
var m,n,s,re,num,cr:longint;
a:array[0..51000] of longint;
b:array[0..51000,0..1] of longint;
pos,sl,cur,d,e,q:array[0..10100] of longint;
free:array[0..10100] of boolean;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
i:=l; j:=r; x:=b[(i+j) div 2,0]; y:=b[(i+j) div 2,1];
repeat
while (b[i,0]<x) or ((b[i,0]=x) and (b[i,1]<y)) do i:=i+1;
while (b[j,0]>x) or ((b[j,0]=x) and (b[j,1]>y)) do j:=j-1;
if i<=j then
begin
t:=b[i,0]; b[i,0]:=b[j,0]; b[j,0]:=t;
t:=b[i,1]; b[i,1]:=b[j,1]; b[j,1]:=t;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;

procedure rf;
var i:longint;
begin
for i:=1 to m do read(b[i,0],b[i,1]);
sort(1,m);
for i:=1 to m do
if (b[i,0]<>b[i-1,0]) or  (b[i,1]<>b[i-1,1]) then inc(sl[b[i,0]]);
pos[1]:=1; cur[1]:=1;
for i:=2 to n+1 do
begin
pos[i]:=pos[i-1]+sl[i-1];
cur[i]:=pos[i];
end;
for i:=1 to m do
if (b[i,0]<>b[i-1,0]) or (b[i,1]<>b[i-1,1]) then
begin
a[cur[b[i,0]]]:=b[i,1];
inc(cur[b[i,0]]);
end;
end;

procedure init;
var i:longint;
begin
for i:=1 to n do
begin
d[i]:=oo; free[i]:=true; e[i]:=0;
end;
end;

procedure pr;
var i,x,y:longint;
begin
init;
cr:=1; num:=1; q[1]:=s;
d[s]:=0; e[s]:=1;
repeat
x:=q[cr];  free[x]:=false;
for i:=pos[x] to pos[x+1]-1 do
begin
y:=a[i];
if free[y] then
begin
if d[y]=oo then
begin
inc(num);
q[num]:=y;
end;
if d[y]=d[x]+1 then e[y]:=2
else
begin
if d[y]>d[x]+1 then
begin
d[y]:=d[x]+1;
e[y]:=e[x];
end;
end;
end;
end;
inc(cr);
until cr>num;
re:=0;
for i:=1 to n do
if e[i]>1 then inc(re);
writeln(re);
end;

begin
rf;
pr;
end.


#### Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

const int N = 10000 + 2;
typedef pair<int, int> ii;
#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
int n, m, s, d[N];
unsigned long long c[N];
vector<vector<int> > g;

void enter() {
scanf("%d%d%d",&n,&m,&s);
g.resize(n); --s;
for(int i = 0, u, v; i < m; ++i) {
scanf("%d%d", &u, &v);
g[--u].push_back(--v);
}
}

void editGraph() {
TR(g, u) {
sort(u->begin(), u->end());
u->resize(distance(u->begin(), unique(u->begin(), u->end())));
}
}

void solve() { //Dijkstra
memset(d, 0x3f, sizeof d); d[s] = 0; c[s] = 1;
priority_queue<ii, vector<ii>, greater<ii> > q; q.push(ii(0, s));
while(!q.empty()) {
int u = q.top().second, du = q.top().first; q.pop();
if(du > d[u]) continue;
TR(g[u], v) {
if(d[*v] > du + 1) q.push(ii(d[*v] = du + 1, *v)), c[*v] = c[u];
else if(d[*v] == du + 1) c[*v] += c[u];
}
}
int res = 0;
for(int u = 0; u < n; ++u) if(d[u] < 0x3f3f3f3f && c[u] >= 2) ++res;
printf("%d\n", res);
}

int main() {
enter();
editGraph();
solve();
return 0;
}


program stable;
uses    math;
type    e=record
x,y:longint;
end;
const   maxm=55555;
maxn=10005;
fi='';
var
check,done:array[1..maxn] of boolean;
n,m,s:longint;

procedure input;
var     inp:text;
i,x,y:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to m do
begin
end;
close(inp);
end;

procedure bfs;
var     i,l,r,u,top,v:longint;

begin
l:=1;r:=1;
q[1]:=s;
check[s]:=true;
way[s]:=1;
while l<=r do
begin
u:=q[l];inc(l);
top:=0;
while i>0 do
begin
if not done[v] then
begin
inc(top);
st[top]:=v;
done[v]:=true;
if not check[v] then
begin
check[v]:=true;
inc(r);
q[r]:=v;
d[v]:=d[u]+1;
way[v]:=way[u];
end
else
begin
if d[u]+1=d[v] then
inc(way[v],way[u]);
if way[v]>1 then way[v]:=2;
end;
end;
end;
for i:=1 to top do
done[st[i]]:=false;
end;
end;

procedure output;
var     i,res:longint;
begin
res:=0;
for i:=1 to n do
if way[i]>1 then inc(res);
write(res);
end;

begin
input;
bfs;
output;
end.


#### Code mẫu của RR

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

#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 MAXN 10111
#define V vector<long>
#define PB push_back
using namespace std;

long n,m,s,cnt[MAXN],trace[MAXN],l[MAXN],q[2][MAXN],top[2];
V ke[MAXN];

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

void solve() {
top[0]=1; q[0][1]=s; cnt[s]=1; l[s]=1;
long now=0;
while (top[now]) {
while (top[now]) {
long u=q[now][top[now]--];
FORV(v,ke[u])
if (trace[*v]!=u)
if (!l[*v]) {
trace[*v]=u;
cnt[*v]=cnt[u];
l[*v]=l[u]+1;
q[1-now][++top[1-now]]=*v;
} else if (l[*v]==l[u]+1) {
trace[*v]=u;
cnt[*v]=min(2L,cnt[*v]+cnt[u]);
}
}
now=1-now;
}
long res=0;
FOR(i,1,n) if (cnt[i]==2) res++;
cout<<res<<endl;
}

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 <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;

vector<int> v[10001];
vector< pair<int,int> > e;
queue<int> q;
int way[10001],len[10001];
bool fr[10001];

int main()
{
int n,m,x,y,s;
//    freopen("stable.in","r",stdin);
//    freopen("stable.out","w",stdout);

scanf("%d%d%d", &n, &m, &s);
for (int i = 0; i < m; i++)
{
scanf("%d%d", &x, &y);
e.push_back(make_pair(x,y));
};
sort(e.begin(),e.end());
v[e[0].first].push_back(e[0].second);
for (int i = 1; i < m; i++) if (e[i] != e[i - 1])
v[e[i].first].push_back(e[i].second);

memset(len, 0, sizeof(len));
memset(way, 0, sizeof(way));
memset(fr, true, sizeof(fr));
fr[s] = false; way[s] = 1;  q.push(s);
while (!q.empty())
{
int a = q.front(); q.pop();
for (int i = 0; i < v[a].size(); i++)
{
int b = v[a][i];
if (fr[b])
{
fr[b] = false; len[b] = len[a] + 1; way[b] = way[a]; q.push(b);
}
else if (len[b] == len[a] + 1)
way[b] = min(200,way[b] + way[a]);
};
};
//    for (int i = 1; i <= n; i++) cout << len[i] << ' ' << way[i] << endl;

int ret = 0;
for (int i = 1; i <= n; i++)
if (way[i] >= 2) ret++;
printf("%d\n", ret);
};


#### Code mẫu của skyvn97

#include<stdio.h>
#include<queue>
#include<vector>
#define MAX 11111
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
const int INF=1e7;
bool a[MAX][MAX];
vi g[MAX];
int n,m,s,r;
int d[MAX];
int c[MAX];
{
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&s);
int i,u,v;
for (i=1;i<=n;i=i+1)
{
d[i]=INF;
c[i]=0;
}
for (i=1;i<=m;i=i+1)
{
scanf("%d",&u);
scanf("%d",&v);
if (a[u][v]) continue;
g[u].push_back(v);
a[u][v]=true;
}
c[s]=1;
d[s]=0;
}
void dijkstra(void)
{
priority_queue<ii,vector<ii>,greater<ii> > q;
q.push(ii(0,s));
while (!q.empty())
{
ii x=q.top();
q.pop();
int i;
int w=x.first;
int u=x.second;
for (i=0;i<g[u].size();i=i+1)
{
if (d[u]+1==d[g[u][i]]) {
c[g[u][i]]+=c[u];
if (c[g[u][i]]>17) c[g[u][i]]=17;
}
else
if (d[u]+1<d[g[u][i]])
{
d[g[u][i]]=d[u]+1;
c[g[u][i]]=c[u];
if (c[g[u][i]]>17) c[g[u][i]]=17;
q.push(ii(d[u]+1,g[u][i]));
}
}
}
int cnt=0;
int i;
for (i=1;i<=n;i=i+1)
if (c[i]>1) cnt++;
printf("%d",cnt);
}
int main(void)
{
dijkstra();
}


#### Code mẫu của khuc_tuan

#include <cstdio>
#include <set>
#include <queue>
using namespace std;

int n, m, s, res;
vector<int> ke[10010];
int d[10010], f[10010];

int main() {
set<pair<int,int> > se;
scanf("%d%d%d", &n, &m, &s);
for(int i=0;i<m;++i) {
int u, v;
scanf("%d%d", &u, &v);
if(!se.count(make_pair(u,v))) {
se.insert(make_pair(u,v));
ke[u].push_back(v);
}
}
queue<int> q;
q.push(s);
d[s] = f[s] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int k=0;k<ke[u].size();++k) {
int v = ke[u][k];
if(d[v] == 0) {
d[v] = d[u] + 1;
f[v] = f[u];
q.push(v);
}
else if(d[v] == d[u] + 1) {
f[v] += f[u];
if(f[v] > 2) f[v] = 2;
}
}
}
for(int i=1;i<=n;++i) if(f[i] >= 2) ++res;
printf("%d\n", res);
return 0;
}