# 題目: 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