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