STNODE - VOI09 Nút st - xung yếu
Tác giả: RR
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <vector>
#define MAXN 10111
#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 V vector<long>
#define PB push_back
using namespace std;
long n,m,s,t,k,queue[MAXN],trace[MAXN],next[MAXN],x[MAXN],lab[MAXN],f[MAXN];
V ke[MAXN];
void inp() {
scanf("%ld %ld %ld %ld",&n,&m,&s,&t);
FOR(i,1,m) {
long u,v;
scanf("%ld %ld",&u,&v);
ke[u].PB(v);
}
}
void bfs() {
long first=1,last=1; queue[1]=s;
while (first<=last) {
long u=queue[first++];
FORV(v,ke[u])
if (!trace[*v]) {
trace[*v]=u;
if (*v==t) return ;
queue[++last]=*v;
}
}
}
void dfs(long u) {
FORV(v,ke[u])
if (lab[*v]) f[u]=max(f[u],lab[*v]);
else {
if (f[*v]) f[u]=max(f[u],f[*v]);
else {
dfs(*v);
f[u]=max(f[u],f[*v]);
}
}
}
void solve() {
trace[s]=s;
bfs();
if (!trace[t]) {
printf("0\n");
return ;
}
long v=t;
while (v!=s) {
long u=trace[v];
next[u]=v;
v=u;
}
long u=s; long k=0;
while (u!=t) {
long v=next[u];
x[++k]=u; lab[u]=k;
u=v;
}
x[++k]=t; lab[t]=k;
FOR(i,1,k) dfs(x[i]);
long res=0,ln=f[x[1]];
FOR(i,2,k-1) {
if (lab[x[i]]>=ln) res++;
ln=max(ln,f[x[i]]);
}
printf("%ld",res);
}
int main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
inp();
solve();
return 0;
}