## Editorial for VOI 09 Bài 2 - Nút st - xung yếu

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

int n, S, T, onPath[10010], prev[10010], flag[10010], mark[10010];
vector <int> a[10010], path;

int bfs()
{
queue <int> q;
prev[S] = -1; q.push(S);
while (!q.empty())
{
int x = q.front(); q.pop();
for (int i = 0; i < int(a[x].size()); i++)
{
int y = a[x][i];
if (!prev[y]) q.push(y), prev[y] = x;
}
}

if (!prev[T]) return 0;

int x = T;
path.push_back(T);
while (x != S) x = prev[x], path.push_back(x);

path.push_back(0);
reverse(path.begin(), path.end());
for (int i = 1; i < int(path.size()); i++) onPath[path[i]] = i;

return 1;
}

int findFurthestOnPath(int x, int z)
{
if (onPath[x] && onPath[x] != z) return onPath[x];
flag[x] = z;
int res = 0;
for (int i = 0; i < int(a[x].size()); i++)
{
int y = a[x][i];
if (flag[y] != z) res = max(res, findFurthestOnPath(y, z));
}
return res;
}

int main()
{
int m, x, y;
cin >> n >> m >> S >> T;
while (m--) scanf("%d%d", &x, &y), a[x].push_back(y);

if (!bfs())
{
puts("0");
return 0;
}

for (int i = 1; i < int(path.size()); i++)
{
int j = findFurthestOnPath(path[i], i);
if (i + 1 < j) mark[i + 1]++, mark[j]--;
}

int ans = 0;
for (int i = 2; i + 1 < int(path.size()); i++)
{
mark[i] += mark[i - 1];
ans += !mark[i];
}

cout << ans << endl;
}


#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;
int num[N], low[N], f[N], lab[N], T[N];
bool was[N], deleted[M];
int n, m, s, t, timer, scc;

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])
}

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

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() {
bfsFindPath();
buildPath();
buildDAG();
dpOnDAG();
solve();
return 0;
}


#### Code mẫu của RR

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


#### Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <cstring>
#define maxn 100005
using namespace std;

bool mark[maxn],next[maxn];
int d[maxn],trace[maxn];
int n,m,s,t;

void BFS(int start) {
memset(d,-1,sizeof(d));
d[start] = 0;
deque<int> q;
q.push_back(start);

while (!q.empty()) {
int u = q.front();
q.pop_front();
for (int i = 0; i < adj[u].size(); i++) {
if (d[v] < 0 || d[v] > d[u] + mark[v]) {
d[v] = d[u] + mark[v];
trace[v] = u;
if (mark[v]) q.push_back(v); else q.push_front(v);
}
}
}
if (d[t] < 0) d[t] = 0;
}

void track(int u) {
next[u] = true;
if (u == s) return;
track(trace[u]);
}

for (int i = 1; i <= n; i++)
if (i != s && i != t && mark[i]) answer.push_back(i);
//  for (int i = 0; i < answer.size(); i++) printf("%d ", answer[i]);
}

int main() {
//  freopen("assassination.in","r",stdin);
scanf("%d %d %d %d", &n, &m, &s, &t);
for (int i = 0; i < m; i++) {
int x,y;
scanf("%d %d", &x, &y);
}
memset(mark,true,sizeof(mark));
while (1) {
int temp = d[t];
BFS(s);
if (d[t] == temp) break;
memset(next,false,sizeof(next));
track(t);
for (int i = 1; i <= n; i++) mark[i] &= next[i];
}
}


#### Code mẫu của skyvn97

#ifndef graph_h
#define graph_h

int calculate(int N, int M, int S, int T, int U[], int V[]);

#endif

#include<bits/stdc++.h>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
using namespace std;
class SegmentTree {
private:
int n;
vector<bool> lazy;
void update(int i,int l,int r,int u,int v) {
if (l>v || r<u || l>r || v<u) return;
if (u<=l && r<=v) {
lazy[i]=true;
return;
}
int m=(l+r)>>1;
update(2*i,l,m,u,v);
update(2*i+1,m+1,r,u,v);
}
public:
SegmentTree() {
n=0;
}
SegmentTree(int n) {
this->n=n;
lazy.assign(4*n+7,false);
}
void update(int l,int r) {
update(1,1,n,l,r);
}
bool get(int x) const {
int i=1;
int l=1;
int r=n;
while (true) {
if (lazy[i]) return (true);
if (l==r) return (false);
int m=(l+r)>>1;
if (x>m) {
i=2*i+1;
l=m+1;
} else {
i=2*i;
r=m;
}
}
}
};
vector<int> path;
int trace[MAX];
int pathPos[MAX];
int n,m,s,t,nComp,cnt;
int low[MAX],num[MAX],compID[MAX];
vector<int> comp[MAX];
stack<int> st;
int storedMaxNode[MAX];
bool bfs(void) {
memset(trace,-1,sizeof trace);
queue<int> q;
trace[s]=0;
q.push(s);
while (!q.empty()) {
int u=q.front();q.pop();
int v=*it;
trace[v]=u;
q.push(v);
}
}
return (trace[t]>0);
}
void findPath(void) {
memset(pathPos,-1,sizeof pathPos);
for (int u=t;u!=s;u=trace[u]) path.push_back(u);
path.push_back(s);
reverse(ALL(path));
REP(i,path.size()) pathPos[path[i]]=i;
}
void dfs(int u) {
low[u]=num[u]=++cnt;
st.push(u);
FORE(it,adj[u]) if (pathPos[*it]<0 && compID[*it]==0) {
int v=*it;
if (num[v]==0) {
dfs(v);
low[u]=min(low[u],low[v]);
} else low[u]=min(low[u],num[v]);
}
if (low[u]==num[u]) {
nComp++;
int v;
do {
v=st.top();st.pop();
compID[v]=nComp;
comp[nComp].push_back(v);
} while (v!=u);
}
}
void tarjan(void) {
FOR(i,1,n) if (pathPos[i]<0 && num[i]==0) dfs(i);
memset(storedMaxNode,-0x3f,sizeof storedMaxNode);
}
int maxNode(int u) {
if (storedMaxNode[u]>=-1) return (storedMaxNode[u]);
int &res=storedMaxNode[u];
res=-1;
if (pathPos[*jt]>=0) res=max(res,pathPos[*jt]);
else if (compID[*jt]!=u) res=max(res,maxNode(compID[*jt]));
}
return (res);
}
int maxPathNode(int u) {
int res=-1;
return (res);
}
int process(void) {
SegmentTree myit((int)path.size()-2);
REP(i,path.size()) {
int j=maxPathNode(path[i]);
if (i+1<=j-1) myit.update(i+1,j-1);
//printf("From %d to %d\n",i,j);
}
int res=0;
FOR(i,1,(int)path.size()-2) if (!myit.get(i)) res++;
return (res);
}
int calculate(int N, int M, int S, int T, int U[], int V[]) {
n=N;m=M;s=S+1;t=T+1;
if (s==t) return (0);
REP(i,m) {
int u=U[i]+1;
int v=V[i]+1;
if (u==s && v==t) return (0);
}
if (!bfs()) return (0);
findPath();
//REP(i,path.size()) printf("%d ",path[i]); printf("\n");
tarjan();
/*FOR(i,1,nComp) {
printf("Comp #%d:",i);
FORE(it,comp[i]) printf(" %d",*it);
printf("\n");
}*/
return (process());
}

#include <stdio.h>

int main() {
//freopen("graph.in","r",stdin);
//freopen("graph.out","w",stdout);

int N,M,S,T; scanf("%d%d%d%d",&N,&M,&S,&T);
S--;T--;
int *U = new int[M];
int *V = new int[M];

for (int i = 0; i < M; i++) {
scanf("%d%d",&U[i],&V[i]);
U[i]--;V[i]--;
}

printf("%d\n",calculate(N,M,S,T,U,V));

return 0;
}


#### Code mẫu của khuc_tuan

#include <iostream>
#include <vector>
using namespace std;

int n, m, s, t, comp;
vector<int> ke[10010 * 2], ds;
int vs[10010 * 2], cant[10010 * 2];

bool dfs(int i) {
if(i==t+n) return true;
if(vs[i]) return false;
vs[i] = true;
for(int k=0;k<ke[i].size();++k) {
int j = ke[i][k];
if(dfs(j)) {
if(i+n==j) cant[i] = j;
ke[j].push_back(i);
ds.push_back(i);
return true;
}
}
return false;
}

void dfs2(int i) {
vs[i] = comp;
for(int k=0;k<ke[i].size();++k)
if(!vs[ke[i][k]] && ke[i][k]!=cant[i]) dfs2(ke[i][k]);
}

int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i=0;i<m;++i) {
int u, v;
scanf("%d%d", &u, &v);
ke[u+n].push_back(v);
}
for(int i=1;i<=n;++i) ke[i].push_back(i+n);
dfs(s);
memset( vs, 0, sizeof(vs));
for(int k=ds.size()-1;k>=0;--k) if(!vs[ds[k]]) {
++comp;
dfs2(ds[k]);
}
int dem = 0;
for(int i=1;i<=n;++i) if(i!=s && i!=t && vs[i] != vs[i+n]) ++dem;
printf("%d\n", dem);
return 0;
}