Module: BFS - 广度行走


Problem

1/6

BFS：开始 (C++)

Theory Click to read/hide

广度优先搜索（BFS）
BFS （广度优先搜索，广度优先搜索）——一种图遍历方法，在简单算法和高级算法中都非常常用。广度优先搜索的工作原理是逐步遍历图形的各个级别，从源节点开始并逐渐远离它。动画中清楚地显示了这一点。
要编写最简单的 BFS ，您需要能够使用一种数据结构，该数据结构允许您从头到尾获取，并能够存储邻接表形式的图（即带有队列）。
 
算法的形式化描述
1) 将开始搜索的顶点编号放入最初为空的队列中。
2) 从队列的开头提取顶点 U 并将其标记为在单独的数组中使用。
3) 在队列的末尾，添加我们可以使用来自顶点U,的边到达 并且尚未标记的所有顶点。
4) 如果队列为空，则连通图的所有节点都扫描完毕，否则返回步骤2。
 
复杂度
由于算法在最坏情况下会访问图的所有节点，当将图存储为邻接表时， 算法的时间复杂度为 O(|V| + |E|) ，其中 V 是图顶点的集合，E 是边的集合。 换句话说，该算法在 number 的最坏情况下有效边数 + 顶点数.

 

Problem

一些村庄之间有道路相连，可以表示为无向图 。此图的顶点是村庄，边是村庄之间的道路（图中可能包含循环）。 已知在 village S 中有一个 artel 小贩。 每天早上，为了出售他们的小杂货店，小贩们会去尚未去过的村庄，并且从现在的村庄到那里有一条路。小贩的队伍总是分组，这样他们一天就可以绕过所有有路的村庄。
小贩们将在多少天内走访所有的村庄？编写一个 BFS 函数，返回任务的答案。

 
输入
第一行包含3个整数n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - 村庄的数量，它们之间的道路数量，以及小贩团伙所在的村庄的数量。  ;在接下来的 m 行中，每行包含 2 个数字 u, v(\(1 < = u, v <= n\ )) - 有道路的两个村庄的数量。村庄索引为 1。

印记
打印一个数字——小贩走遍所有村庄需要多少天。

 

例子
<头> <日># <正文>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
输入 输出
1 6 7 1
1 2
15
23
5 4
34
36
4 6		 4
Write the program below 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>

using namespace std;

vector<bool> used;   
// used[i] = true, если мы были в вершине i
vector<vector<int> > g;   // список смежности
vector<int> tm;     
// tm[i] - день, когда в деревню i 
// пришла артель коробейников
int n, m, s;

int bfs()
{                   
}

int main()
{
	cin >> n >> m >> s;
	s--;
	g.resize(n);
	tm.resize(n);
	used.assign(n, false);
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	cout << bfs();
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!