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;
}

Download