STNODE - VOI09 Nút st - xung yếu
Tác giả: ll931110
Ngôn ngữ: C++
#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];
vector<int> adj[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++) {
int v = adj[u][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]);
}
void printAnswer() {
vector<int> answer;
for (int i = 1; i <= n; i++)
if (i != s && i != t && mark[i]) answer.push_back(i);
printf("%d\n", answer.size());
// 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);
adj[x].push_back(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];
}
printAnswer();
}