STNODE - VOI09 Nút st - xung yếu
Tác giả: flashmt
Ngôn ngữ: C++
#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;
}