VOJ - STNODE

Source: STNODE
Tags: Graph

Problem:
Cho N đỉnh và M đường đi 1 chiều giữa các cặp đỉnh, 2 thành phố bất kỳ không có quá 1 đường đi 1 chiều, và 2 đỉnh s, t. Các nút st-xung yếu là các đỉnh mà mọi đường đi từ s đến t đều phải đi qua chúng. Đếm số lượng nút st-xung yếu.
3 ≤ N ≤ 1e4.
M ≤ 1e5.

Ví dụ:
Input:
7 10 1 5
1 2
1 3
3 4
4 5
5 6
6 2
6 7
7 3
7 5

Output:
1

Explanation:

Nút màu đỏ là nút st-xung yếu

Solution:
Chọn một con đường bất kỳ đi từ s đến t, bằng DFS hoặc BFS, các nút st-xung yếu chắc chắn phải nằm trên con đường đó. Giải thích điều này thì đơn giản, các nút st-xung yếu là các nút xuất hiện trong mọi đường đi, do đó hướng làm của chúng ta là liệt kê ra một đường đi bất kỳ và tìm cách loại bỏ những nút không phải st-xung yếu, thu hẹp phạm vi xử lý lại.

Ta có một đường đi từ s đến t (đường màu xanh trên hình), và u, v là 2 nút trên đường đi đó, nếu u có đường đi khác đến v, thì các nút ở giữa u và v không phải là nút st-xung yếu vì đã tồn tại một đường đi khác không chứa chúng. Vậy một nút u được gọi là nút st-xung yếu sẽ có tính chất như sau: trên đường đi từ s đến t, các nút trước u không có đường đi nào đến các nút sau u. Vậy để kiểm tra điều này, với mỗi nút ta tìm nút xa nhất có thể với tới bằng các đường đi khác, bằng DFS hoặc BFS, cập nhật lại thường xuyên. Vì với mỗi đỉnh ta chỉ DFS hoặc BFS một lần, do đó sẽ không bị TLE và độ phức tạp vẫn là O(N + M).

Code:
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n, m, s, t, _prev[10015], on_path[10015], cnt;
vector <int> a[10015], node;
queue <int> bfs;
bool visited[10015];

int main() {
    cin >> n >> m >> s >> t;
    for (int u, v; m--;)
        cin >> u >> v,
        a[u].push_back(v);
    bfs.push(s);
    while (!bfs.empty()) {
        int u = bfs.front();
        bfs.pop();
        for (int i = 0; i < a[u].size(); i++)
            if (a[u][i] != s && !_prev[a[u][i]])
                _prev[a[u][i]] = u,
                bfs.push(a[u][i]);
    }
    for (int u = t; u; node.push_back(u), u = _prev[u]);
    reverse(node.begin(), node.end());
    for (int i = 0; i < node.size(); i++)
        on_path[node[i]] = i + 1;
    for (int i = 0, x = 0; i < node.size(); i++) {
        cnt += (node[i] != s && node[i] != t && x <= i + 1);
        bfs.push(node[i]);
        while (!bfs.empty()) {
            int u = bfs.front();
            bfs.pop();
            for (int i = 0; i < a[u].size(); i++)
                if (!visited[a[u][i]]) {
                    if (on_path[a[u][i]])
                        x = max(x, on_path[a[u][i]]);
                    else
                        visited[a[u][i]] = true,
                        bfs.push(a[u][i]);
                }
        }
    }
    cout << cnt;

}