CCF 201709 4

2022-09-23 00:13:10 字數 1513 閱讀 4809

這裡有幾篇比較好的解題思路的部落格:

【圖論--dfs】ccf 201709-4 通訊網路 :內含回溯思路

ccf 2017-09-04 通訊網路 圖的遍歷

試題編號:

201709-4

試題名稱:

通訊網路

時間限制:

1.0s

記憶體限制:

256.0mb

問題描述:

問題描述

某國的軍隊由n個部門組成,為了提高安全性,部門之間建立了m條通路,每條通路只能單向傳遞資訊,即一條從部門a到部門b的通路只能由a向b傳遞資訊。資訊可以通過中轉的方式進行傳遞,即如果a能將資訊傳遞到b,b又能將資訊傳遞到c,則a能將資訊傳遞到c。一條資訊可能通過多次中轉最終到達目的地。

由於保密工作做得很好,並不是所有部門之間都互相知道彼此的存在。只有當兩個部門之間可以直接或間接傳遞資訊時,他們才彼此知道對方的存在。部門之間不會把自己知道哪些部門告訴其他部門。

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

現在請問,有多少個部門知道所有n個部門的存在。或者說,有多少個部門所知道的部門數量(包括自己)正好是n。

輸入格式

輸入的第一行包含兩個整數n, m,分別表示部門的數量和單向通路的數量。所有部門從1到n標號。

接下來m行,每行兩個整數a, b,表示部門a到部門b有一條單向通路。

輸出格式

輸出一行,包含一個整數,表示答案。

樣例輸入

4 41 2

1 32 4

3 4樣例輸出

2樣例說明

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

評測用例規模與約定

對於30%的評測用例,1 ≤ n ≤ 10,1 ≤ m ≤ 20;

對於60%的評測用例,1 ≤ n ≤ 100,1 ≤ m ≤ 1000;

對於100%的評測用例,1 ≤ n ≤ 1000,1 ≤ m ≤ 10000。

#include#include

#include

using

namespace

std;

int a[1005][1005];//

鄰接矩陣

int vis[1005];//

訪問標記結點

vector v[1005];//

鄰接表

void dfs(int x,int

y) }

return;}

intmain()

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

int flag,tot=0

;

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

}if(flag) tot++;

}printf("%d

",tot);

return0;

}

CCF CSP 201709 1 打醬油 (貪心)

問題描述 試題編號 201709 1 試題名稱 打醬油時間限制 1 0s 記憶體限制 256 0mb 問題描述 問題描述 小明帶著n元錢去買...

CCF201604 4 遊戲

試題編號 201604 4 試題名稱 遊戲時間限制 1 0s 記憶體限制 256 0mb 問題描述 問題描述 小明在玩一個電腦遊戲,遊戲在一個n m的方格圖上進行,小明控制的角色開始的時候站在第一行第一列,目標是前往第n行第m列。 方格圖上有一些方格是始終安全的,有一些在一段時間是危險的,如果小明控制...

CCF201604 4 遊戲

試題編號 201604 4 試題名稱 遊戲時間限制 1 0s 記憶體限制 256 0mb 問題描述 問題描述 小明在玩一個電腦遊戲,遊戲在一個n m的方格圖上進行,小明控制的角色開始的時候站在第一行第一列,目標是前往第n行第m列。 方格圖上有一些方格是始終安全的,有一些在一段時間是危險的,如果小明控制...