# 題目: UVa 924 - Spreading the News
# 題目說明
每個人每天會將新消息告訴朋友
寫一個程式去找出以下兩項
- 最多人知道消息那一天的人數
- 最大人數發生的最早那一天
INPUT:
第一行會有一個整數 E
,代表人數,由 0
編號至 E - 1
接下來會有 E
行,代表 0
至 E - 1
的朋友
每行會有一個整數 N
,代表朋友的人數,之後會有 N
個整數,代表朋友的編號
接著會有一個整數 T
,代表有幾個 cases,之後會有 T
個整數,代表從他開始傳遞
OUTPUT:
輸出最大人數及最大人數最早發生的那一天
如果最大人數為 0
,則不需要輸出後者
# 解題方法
先建表,之後進行 bfs,儲存傳遞的天數及最大數量,最後再找最大值輸出
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <queue> | |
using namespace std; | |
vector< vector<int> > G; | |
vector<bool> vis; | |
vector<int> dep; | |
vector<int> day; | |
void bfs(int st) | |
{ | |
queue<int> Q; | |
Q.emplace(st); | |
vis[st] = true; | |
dep[st] = 0; | |
while (!Q.empty()) | |
{ | |
int u = Q.front(); | |
Q.pop(); | |
for (auto& v : G[u]) if (!vis[v]) | |
{ | |
vis[v] = true; | |
Q.emplace(v); | |
dep[v] = dep[u] + 1; | |
++day[dep[v]]; | |
} | |
} | |
pair<int, int> max; | |
for (int i = 1; i < day.size(); ++i) | |
{ | |
if (day[i] > max.first) | |
{ | |
max.first = day[i]; | |
max.second = i; | |
} | |
} | |
cout << max.first; | |
if (max.first) cout << ' ' << max.second; | |
cout << "\n"; | |
} | |
int main() | |
{ | |
// fast io | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int E, T, st; | |
cin >> E; | |
G.assign(E, vector<int>()); | |
// store friend's data | |
for (int i = 0, N, u; i < E; ++i) | |
{ | |
cin >> N; | |
while (N--) cin >> u, G[i].emplace_back(u); | |
} | |
cin >> T; | |
while (T--) | |
{ | |
vis.assign(E + 1, false); | |
dep.assign(E + 1, 0); | |
day.assign(E + 1, 0); | |
cin >> st; | |
bfs(st); | |
} | |
return 0; | |
} |
# 參考文章:
https://tnlolicon.blogspot.com/2018/12/uva-924spreading-news.html
https://github.com/morris821028/UVa/blob/master/volume009/924%20-%20Spreading%20The%20News.cpp