首頁

Difficulty:

⭐️⭐️⭐️

# Problem Description 題敘:

謠言問題 Link

給你一張無向圖，有 NN 個點以及 MM 條邊，再給定一個點 甲，甲 在收到消息後會傳給跟他有邊關係的點，而得到消息的點 也會把消息繼續傳播給跟他有關係的點，要求你選定一個點 乙 ，使得最後傳遞到消息的人數最少。乙 若收到消息便不會再繼續傳遞下去。

# 輸出:

請輸出 乙 的編號以及最後獲得消息的人數。若不管有沒有選擇 乙，最後會的知消息的人數皆相同，那麼請輸出 00.

# Thinking 思考歷程:

看到題目第一個想法是 直接 DFS 一遍就可以知道不選擇任何 乙 的總傳播點數，之後再每個可能的 乙 都試過一遍，看誰當 乙 ，拔掉該點後的點數量會最小，不過這種 O(n(n+m))O(n(n+m)) 的算法就不用奢求會過。

肯定要一個 O(n+m)O(n+m) 的算法。 那如果我們找的 乙 有最多的邊呢？好像也不正確，畫一下極端的例子也可以推翻。

那，ㄝ，聚焦了一下，發現了這張圖可能有許一塊一塊的連通區塊，那麼 乙 應該要跟 甲 是想同的連通區塊。所以之需要關注跟 甲 同樣連通區塊的點。接著就是，我猜測 乙 跟甲一定要有邊的關係，否則一定能找到更好的解，但這應該不是重點就是了。

(作弊作弊，看題解

# Solution 題解:

破題：由於乙點的目標是 阻斷甲 的訊息傳播途徑，其實就是要在有包括甲在內的連通區塊 XX 中 求一個 割點，使得 <span style="color: red;"> 拔掉乙後，剩下的點數盡量最小。</span>

Okay，所以目標是要找到所有割點，紀錄並比較一下他們的後代數量， 再用 XX 的總點數 扣掉後代數量最多的割點 就是我們的答案 ... ?

不對，儘管一個割點 CC 他的後代數量很多，然而萬一 CC 的後代都跟 甲 相連，那麼 CC 就不一定是正確的割點。這也代表說，若你的後代是可以不藉你就可以往上爬到更高祖先的話，這樣就計算上會多算很多子代。因此，我們真正要記錄的是一個割點 有多少子孫沒辦法不就藉由他到達更高的祖先， 即 拔掉 CC 後總共會拔掉的點數，最後再用 XX 的總點數 扣掉數量最大的就會是我們的答案。

據此，我們可以用 ncnt[] 這個陣列來記錄這件事。那 在 DFS 當中，若確定 CC 是割點，那 ncnt[C] 是不是可以直接繼承後代的 ncnt[] ，再加上自己那點呢？

也不盡然正確，這樣會少記錄到某些點，考慮這個 DFS Tree，如下圖:

假設 44 為 甲 (Root)。我們可以發現，若節點 33 只繼承小孩 11 跟 小孩 66 的 ncnt[] 的話，加上自己後， ncnt[3] 會發現數量只有 44 個，為1,6,2,31,6,2,3 。很明顯，少掉了節點 55 ! 因為節點 11 在紀錄時 節點 55 可以再往上爬到節點 33 ，所以節點 11 就只有記錄到他自己。所以現在 在紀錄 33 時，節點 55 沒辦法再更往上爬了，應該要被拔掉，卻沒被記錄到。

換個想法，我們可以多開幾個變數。對於一個點 VV ，我們用 sum 紀錄 VV 子樹的總數量，再用 children 記錄 VV 該子代的子樹的數量，若 VV 有一子樹無法不藉由他就能爬到更高的祖先的話，VV 就會是割點，並且 ncnt[v] += chilren 。

如此就能很輕鬆的維護好 ncnt[] ，最後只要特判一下若有好幾個 maxmax 的話，要取字典序最小的。

至於答案 00 的情形怎麼辦呢？其實原因是 有甲點的連通區塊應該是個 BCC，即 沒有割點 ， 不管拔掉哪一個點都無法讓圖變得不連通，這種情形特判一下就可以了。

最後還有一點不同於一般的割點求法，就是我們不用特判根是否是割點的情形，因為題目規定，要另求一個 乙，不能甲跟乙是同個人。也合理，如果甲跟乙可是同一個人，那麼根本不用算。

# AC Code 程式碼:

#include <bits/stdc++.h>
using namespace std;
const int oo = 2000000000; // 2e9
const int N = 3e4+4;
int n,m,k, ncnt[N] = {}, visited[N] = {}, depth[N], low[N], cutv[N] = {}; 
vector<int> g[N]; // cutv - saves all cut v
int dfs(int v, int p){
    int sum; // 紀錄 v 以及 其子樹的總數量
    sum = ncnt[v] = visited[v] = 1;
    low[v] = depth[v] = ~p ? depth[p] + 1 : 0;
    for(auto u : g[v]){
        if(u == p) continue;
        if(visited[u]) { // back edge
            low[v] = min(low[v], depth[u]);
        }
        else{ // tree edge
            int children = dfs(u, v);
            sum += children;
            low[v] = min(low[v], low[u]);
            if(low[u] >= depth[v] && v != k) { // cut vertex
                cutv[v] = 1;
                ncnt[v] += children; 
            }
        }
    }
    return sum;
}
int main(){ IOS
    cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b); g[b].push_back(a);
    }
    cin>>k;
    int sum = dfs(k, -1);
    int mx = -oo, tar = oo;
    for(int i = 1; i<=n; i++) if(cutv[i]){
       if(ncnt[i] > mx){
           mx = ncnt[i];
           tar = i;
       }
    }
    //if 沒有割點
    if(mx == -oo) cout<<0<<'\n';
    else cout<<tar<<' '<<(sum-mx+1)<<'\n';
}
<br/>
# 學習到的新技巧 or 概念～
  • Tarjan 求割點
  • 圖的連通