CCF計算機(jī)職業(yè)資格認(rèn)證考試題解系列文章為meelo原創(chuàng)，請務(wù)必以鏈接形式注明本文地址

CCF CSP 201709-4 通信網(wǎng)絡(luò)

問題描述

某國的軍隊(duì)由N個部門組成，為了提高安全性，部門之間建立了M條通路，每條通路只能單向傳遞信息，即一條從部門a到部門b的通路只能由a向b傳遞信息。信息可以通過中轉(zhuǎn)的方式進(jìn)行傳遞，即如果a能將信息傳遞到b，b又能將信息傳遞到c，則a能將信息傳遞到c。一條信息可能通過多次中轉(zhuǎn)最終到達(dá)目的地。
由于保密工作做得很好，并不是所有部門之間都互相知道彼此的存在。只有當(dāng)兩個部門之間可以直接或間接傳遞信息時，他們才彼此知道對方的存在。部門之間不會把自己知道哪些部門告訴其他部門。

image.png

上圖中給了一個4個部門的例子，圖中的單向邊表示通路。部門1可以將消息發(fā)送給所有部門，部門4可以接收所有部門的消息，所以部門1和部門4知道所有其他部門的存在。部門2和部門3之間沒有任何方式可以發(fā)送消息，所以部門2和部門3互相不知道彼此的存在。
現(xiàn)在請問，有多少個部門知道所有N個部門的存在。或者說，有多少個部門所知道的部門數(shù)量（包括自己）正好是N。

輸入格式

輸入的第一行包含兩個整數(shù)N, M，分別表示部門的數(shù)量和單向通路的數(shù)量。所有部門從1到N標(biāo)號。
接下來M行，每行兩個整數(shù)a, b，表示部門a到部門b有一條單向通路。

輸出格式

輸出一行，包含一個整數(shù)，表示答案。

樣例輸入

4 41 21 32 43 4

樣例輸出

2

樣例說明

部門1和部門4知道所有其他部門的存在。

評測用例規(guī)模與約定

對于30%的評測用例，1 ≤ N ≤ 10，1 ≤ M ≤ 20；
對于60%的評測用例，1 ≤ N ≤ 100，1 ≤ M ≤ 1000；
對于100%的評測用例，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000。

解析

如果圖無環(huán)，計算每一個頂點(diǎn)父節(jié)點(diǎn)的個數(shù)及子節(jié)點(diǎn)的個數(shù)，如果二者只和加一等于總節(jié)點(diǎn)的個數(shù)，那么就是所求解的知道N個節(jié)點(diǎn)存在的節(jié)點(diǎn)。
這一步可以通過N個深度優(yōu)先搜索得到。從每一個節(jié)點(diǎn)開始進(jìn)行深度優(yōu)先搜索，每到達(dá)一個節(jié)點(diǎn)，該節(jié)點(diǎn)的計數(shù)加一。復(fù)雜度為O(V(V+E))
如果圖存在環(huán)，則需進(jìn)行強(qiáng)連通分量的分解。代碼中使用了Kosaraju算法進(jìn)行強(qiáng)連通分量的分解。復(fù)雜度為O(V+E)
分解后得到每一個頂點(diǎn)的強(qiáng)連通分量標(biāo)號。
然后計算每一個節(jié)點(diǎn)父強(qiáng)連通分量的個數(shù)與子強(qiáng)連通分量的個數(shù)。這一步從每一個強(qiáng)連通分量中選擇一個頂點(diǎn)開始進(jìn)行深度優(yōu)先搜索，如果當(dāng)前所在強(qiáng)連通分量的標(biāo)簽與起始節(jié)點(diǎn)強(qiáng)連通分量標(biāo)簽不同，則該節(jié)點(diǎn)計數(shù)加一。
如果一個頂點(diǎn)父強(qiáng)連通分量的個數(shù)加上子強(qiáng)連通分量的個數(shù)加一等于總強(qiáng)連通分量個數(shù)，那么這個節(jié)點(diǎn)知道所有節(jié)點(diǎn)的存在。

代碼

C++

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX_V 1001
using namespace std;

int N, M;
vector<int> G[MAX_V], rG[MAX_V];
vector<int> postorder;
bool used[MAX_V];
int label[MAX_V];
int sccv[MAX_V]; // 每一個強(qiáng)連通分量的一個頂點(diǎn) 
int nparent[MAX_V], nchild[MAX_V];  // 每一個節(jié)點(diǎn)父/子強(qiáng)連通分量個數(shù) 

// 生成圖的后序遍歷 
void dfs(int u) {
    for(int i=0; i<G[u].size(); i++) {
        int v = G[u][i];
        if(!used[v]) {
            used[v] = true;
            dfs(v);
        }
    }
    postorder.push_back(u);
}

int rdfs(int u, int l) {
    label[u] = l;
    for(int i=0; i<rG[u].size(); i++) {
        int v = rG[u][i];
        if(!used[v]) {
            used[v] = true;
            rdfs(v, l);
        }
    }
}

// Kosaraju算法 分解強(qiáng)連通分量 
int SCC() {
    fill(used, used+MAX_V, 0);
    for(int n=1; n<=N; n++) {
        if(!used[n]) {
            used[n] = true;
            dfs(n);
        }
    }
    fill(used, used+MAX_V, 0);
    int l = 0;
    for(int n=N-1; n>=0; n--) {
        int v = postorder[n];
        if(!used[v]) {
            l++;
            used[v] = true;
            rdfs(v, l);
            sccv[l] = v;
        }
    }
    return l;
}

// 統(tǒng)計u所在強(qiáng)連通分量能夠到達(dá)的其它強(qiáng)連通分量 
void dfs2(int u, int l, int (&nparent)[MAX_V], vector<int> (&G)[MAX_V]) {
    if(label[u] != l) nparent[u]++;
    for(int i=0; i<G[u].size(); i++) {
        int v = G[u][i];
        if(!used[v]) {
            used[v] = true;
            dfs2(v, l, nparent, G);
        }
    }
}


int main() {
    cin >> N >> M;
    for(int m=0; m<M; m++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        rG[b].push_back(a);
    }
    
    int numc = SCC();
    
    // 統(tǒng)計每一個節(jié)點(diǎn)父強(qiáng)連通分量個數(shù) 
    for(int i=1; i<=numc; i++) {
        fill(used, used+MAX_V, 0);
        int v = sccv[i];
        used[v] = true;
        dfs2(v, label[v], nparent, G);
    }
    
    // 統(tǒng)計每一個節(jié)點(diǎn)子強(qiáng)連通分量個數(shù) 
    for(int i=1; i<=numc; i++) {
        fill(used, used+MAX_V, 0);
        int v = sccv[i];
        used[v] = true;
        dfs2(v, label[v], nchild, rG);
    }
    
    int cnt = 0;
    for(int n=1; n<=N; n++) {
        // 如果父強(qiáng)連通分量個數(shù)加子強(qiáng)連通分量個數(shù)加一等于總強(qiáng)連通分量個數(shù) 
        if(nparent[n]+nchild[n]+1==numc) cnt++;
    }
    cout << cnt;
}