題目 + 解法

這是 CodeForces Round 490 div.3 的題目 最近因為 div.3（水題上分 round）的緣故，不小心搭上 rating 通膨的潮流，上了藍人 沒有意外下一場應該就會下來了吧 先放上題目連結

會寫這題的緣故是因為有某位捧油說他不會寫，前天在台北 ytp 的時候稍微提了下 今天想說把它寫成一篇題解吧，等等寫完剛好可以去看昨天 Education Round 的 Final Standing（雖然我沒打）

講一下題目大意好了 首先，給定一張圖有 $N$ 個點、$M$ 條單向邊，並給定一點 $S$ 求現在這張圖還需要加上幾條邊（當然也是單向的），才可以使 $S$ 與此圖上的任意一點$U$有單向路徑（ $S$ 到 $U$ ）

有個很直觀的想法如下，首先點會先被分成兩種類型：

1. 這些點都可以從 $S$ 到達——也就是說，從 $S$ 開始 dfs ，這些點都會經過
2. 沒有經過的點（從 $S$ 出發到達不了）

所以要讓剩下的點都可以從 $S$ 到達，那就把邊接在類型2的那些點的頭（從這個點回朔到最頂端的點，有點樹鍊剖分的感覺），不就是最少新增邊的數量了？ （因為這些點的頂點可能會重複——即便沒有重複。。。這些點總還是要連接上去吧）

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

#pragma GCC optimize ( "O3" )
#pragma loop_opt ( on )

using namespace std;

#define maxN 5005

vector < int > edges[maxN];
int pa[maxN];
bool used[maxN];

void dfs ( int n, int p ){
    used[n] = true;
    pa[n] = p;
    for ( auto i: edges[n] ){
        if ( used[i] )
            continue;
        dfs ( i, p );
    }
}

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

    int n, m, s, u, v;
    cin >> n >> m >> s;
    while ( m-- ){
        cin >> u >> v;
        edges[u].push_back ( v );
    }

    dfs ( s, s );
    for ( int i = 1 ; i <= n ; i++ ){
        if ( pa[i] == 0 ){
            memset ( used, 0, sizeof used );
            dfs ( i, i );
        }
    }

    set < int > lib;
    for ( int i = 1 ; i <= n ; i++ ){
        if ( pa[i] != s )
            lib.insert ( pa[i] );
    }

    cout << lib.size() << '\n';
}

tips

可能有些人會有這個疑問：為甚麽我要在每次 dfs 前都把 used（記錄是否已經經過）清空，這樣不是會把某些點的 pa（記錄最頂頭的點是哪個）洗掉嗎，如果那些點已經是可以從 $S$ 到達的，這樣不是有可能會多算？

是這樣的：我會從這個點開始 dfs，代表我還不確定他的最頂（pa）在哪，意思就是說，我必須要在這個點以及 $S$ 之間加上一條邊，這還挺合理的吧（？

又，只要我在這個點以及 $S$ 之間加上一條邊了，那麼我好像也不用擔心他的子結點了，反正都會走到 所以即便 pa 被覆寫了也是沒有關係的