問題描述

某國(guó)的軍隊(duì)由N個(gè)部門組成，為了提高安全性，部門之間建立了M條通路，每條通路只能單向傳遞信息，即一條從部門a到部門b的通路只能由a向b傳遞信息。信息可以通過中轉(zhuǎn)的方式進(jìn)行傳遞，即如果a能將信息傳遞到b，b又能將信息傳遞到c，則a能將信息傳遞到c。一條信息可能通過多次中轉(zhuǎn)最終到達(dá)目的地。

由于保密工作做得很好，并不是所有部門之間都互相知道彼此的存在。只有當(dāng)兩個(gè)部門之間可以直接或間接傳遞信息時(shí)，他們才彼此知道對(duì)方的存在。部門之間不會(huì)把自己知道哪些部門告訴其他部門。

上圖中給了一個(gè)4個(gè)部門的例子，圖中的單向邊表示通路。部門1可以將消息發(fā)送給所有部門，部門4可以接收所有部門的消息，所以部門1和部門4知道所有其他部門的存在。部門2和部門3之間沒有任何方式可以發(fā)送消息，所以部門2和部門3互相不知道彼此的存在。

現(xiàn)在請(qǐng)問，有多少個(gè)部門知道所有N個(gè)部門的存在。或者說，有多少個(gè)部門所知道的部門數(shù)量(包括自己)正好是N。

輸入格式

輸入的第一行包含兩個(gè)整數(shù)N, M，分別表示部門的數(shù)量和單向通路的數(shù)量。所有部門從1到N標(biāo)號(hào)。

接下來M行，每行兩個(gè)整數(shù)a, b，表示部門a到部門b有一條單向通路。

輸出格式

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

樣例輸入

4 4

1 2

1 3

2 4

3 4

樣例輸出

2

樣例說明

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

評(píng)測(cè)用例規(guī)模與約定

對(duì)于30%的評(píng)測(cè)用例，1 ≤ N ≤ 10，1 ≤ M ≤ 20；

對(duì)于60%的評(píng)測(cè)用例，1 ≤ N ≤ 100，1 ≤ M ≤ 1000；

對(duì)于100%的評(píng)測(cè)用例，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000。

分析：

一個(gè)節(jié)點(diǎn)通知和被通知都會(huì)互相知道對(duì)方的存在

一個(gè)部門知道其他所有部門才算作目標(biāo)節(jié)點(diǎn)

以每個(gè)節(jié)點(diǎn)為起點(diǎn)，正向和反向分別遍歷一遍圖，記錄訪問到的節(jié)點(diǎn)編號(hào)

// BFS or DFS

#include

using namespace std;

const int maxn = 1005;

int n,m;

vectorv[2][maxn];

int vis[2][maxn];

void input()

{

cin>>n>>m;

while(m--)

{

int from,to;

cin>>from>>to;

v[0][from].push_back(to);

v[1][to].push_back(from);

}

}

queueq;

// V2 BFS 562ms

void solve(int now,int x)

{

while(!q.empty()) q.pop();

q.push(now);

while(!q.empty())

{

int k = q.front();

q.pop();

if(vis[x][k]) continue;

// 這里一定要對(duì)vis進(jìn)行判斷，因?yàn)橄旅娴难h(huán)可能導(dǎo)致一個(gè)點(diǎn)多次入隊(duì) !

vis[x][k]=1;

int num = v[x][k].size();

for(int i=0;i

{

int to = v[x][k][i];

if(vis[x][to]) continue;

q.push(to);

}

}

}

// V3 使用DFS 265ms 100

//可以調(diào)整代碼，只遍歷一次 ： flag[i][j] 表示i能訪問到j(luò)這樣一次遍歷就能記錄到需要的信息，我使用vis判斷是否訪問，這樣的記錄方式局限在只能記錄一方的信息

/*

void solve(int now,int x)

{

vis[x][now]=1;

for(int i=0;i

{

if(!vis[x][v[x][now][i] ]) solve(v[x][now][i],x);

}

}*/

int main()

{

input();

int num=0;

for(int i=1;i<=n;i++)

{

memset(vis,0,sizeof(vis));

for(int j=0;j<2;j++)

solve(i,j);

int in=0;

for(int j=1;j<=n;j++)

if(vis[0][j]|vis[1][j]) in++;

if(in==n)num++;

}

cout<

return 0;

}

原文：https://www.cnblogs.com/star-and-me/p/9648839.html

總結(jié)

以上是生活随笔為你收集整理的csp 通信网络 java_CSP 通信网络的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。