STNODE - VOI09 Nút st - xung yếu

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 10005;
const int M = 100005;
using namespace std;
VI super[N], adj[N], a[N];
int num[N], low[N], f[N], lab[N], T[N];
bool was[N], deleted[M];
int n, m, s, t, timer, scc;

void readInput() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> s >> t;
    int u, v;
    FOR(i, 0, m) {
        cin >> u >> v;
        a[u].PB(v);
    }
}
void bfsFindPath() {
    queue<int> Q;
    Q.push(s); T[s] = -1;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        TR(it, a[u]) if (T[*it] == 0) {
            T[*it] = u;
            if (*it == t) return;
            Q.push(*it);
        }
    }
}

VI path;
bool inPath[N];
int id[N];
void buildPath() {
    for(int v = t; v != s; v = T[v]) path.PB(v);
    path.PB(s);
    reverse(ALL(path));
    FOR(i, 0, SZ(path))
        inPath[path[i]] = 1, id[path[i]] = i;
}

stack<int> S;
void dfsTarjan(int u) {
    num[u] = low[u] = ++timer; S.push(u);
    TR(it, a[u]) {
        int v = *it;
        if (was[v] || inPath[v]) continue;
        if (num[v]) low[u] = min(low[u], num[v]);
        else {
            dfsTarjan(v);
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] >= num[u]) {
        int v;
        do {
            v = S.top(); S.pop();
            was[v] = 1;
            lab[v] = scc;
            super[scc].PB(v);
        } while (v != u);
        scc++;
    }
}

void buildDAG() {
    REP(i, 1, n)
    if (!was[i]) dfsTarjan(i);
    FOR(i, 0, scc)
        TR(u, super[i]) TR(it, a[*u])
        if (!inPath[*it])
            adj[i].PB(lab[*it]);
}

void dpOnDAG() {
    FOR(i, 0, scc) {
        TR(u, super[i]) TR(it, a[*u])
        if (inPath[*it]) f[i] = max(f[i], id[*it]);

        TR(u, adj[i])
            f[i] = max(f[i], f[*u]);
    }
}

int in[N], out[N];
void solve() {
    FOR(i, 0, SZ(path)) {
        int right = f[lab[path[i]]] - 1;
        if (right > i) {
            in[i + 1]++;
            out[right]++;
        }
    }
    int cnt = 0, ans = SZ(path) - 2;
    FOR(i, 0, SZ(path)) {
        cnt += in[i];
        if (cnt) ans--;
        cnt -= out[i];
    }
    cout << ans;
}

int main() {
    readInput();
    bfsFindPath();
    buildPath();
    buildDAG();
    dpOnDAG();
    solve();
    return 0;
}

Download