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