# 題目: UVa 924 - Spreading the News

# 題目說明

每個人每天會將新消息告訴朋友
寫一個程式去找出以下兩項

  • 最多人知道消息那一天的人數
  • 最大人數發生的最早那一天

INPUT:
第一行會有一個整數 E ,代表人數,由 0 編號至 E - 1
接下來會有 E 行,代表 0E - 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