STABLE - VOI10 - Ổn định
Tác giả: RR
Ngôn ngữ: C++
#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;
}