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

一部の村は道路でつながっており、無向グラフとして表すことができます。このグラフの頂点は村であり、端は村の間の道路です (グラフには循環が含まれる場合があります)。  村では  S のアルテル 行商人. 毎朝、小さな小間物を売るために、行商人は まだ行ったことのない村に行きますが、そこには現在の村から道があります。行商人のアルテルは、現在の村から道路があるすべての村を 1 日で回れるように、常にグループに分かれています。
行商人は何日ですべての村を訪れますか?タスクに答えを返す BFS 関数を書きます。

 
入力
最初の行には、3 つの整数 n、m、s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - 村の数、村の間の道路の数、行商人のギャングが本拠を置く村の数.  ; 次の m< /code> 行には、それぞれ u、v(\(1 < = u, v <= n\ )) - 間に道路がある 2 つの村の数。村は 1 でインデックスされます。

インプリント
行商人がすべての村を訪れるのに何日かかるか、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!