Hướng dẫn giải của Cáp treo 2

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Đảo hướng của các cạnh. Ta sẽ nối trực tiếp các cạnh từ ~T~ đến các đỉnh khác.

Những đỉnh đã thăm sẽ đánh dấu ~vis_i = true~. DFS một lần từ ~T~, những đỉnh đến được chắc chắn không cần được nối.

Với những đỉnh còn lại chưa được thăm. Xét đỉnh ~i~, giả sử ta sẽ nối đỉnh này với ~T~, DFS từ đỉnh này, những đỉnh nó có thể thăm chắc chắn không cẩn được nối và sẽ được đánh dấu đã thăm. Sau khi DFS xong thì phải đánh dấu ~i~ là chưa thăm vì có thể trong tương lại sẽ có đỉnh khác được nối với ~T~ và nó sẽ dẫn đến ~i~. Đáp án bài toán là số lượng đỉnh có ~vis_j=0~.

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 69;

int n, m, t;

vector<int> edge[maxn];
int vis[maxn];

void dfs(int root){
    vis[root] = 1;
    for(int v: edge[root])
        if(!vis[v])
            dfs(v);
}   

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m >> t;
    for(int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        if(b != a) edge[b].push_back(a);
    }

    dfs(t);
    for(int i = 1; i <= n; i++){
        if(!vis[i]) dfs(i), vis[i] = false;
    }


    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(!vis[i]) cnt++;
    }
    cout << cnt;
}