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

Download