Module: BFS - Umgehung in der Breite


Problem

1/6

BFS: Anfang (C++)

Theory Click to read/hide

Prüfung in der BreiteBFS)
BFS (siehe Breite, Brot-Erste Suche() - die Art, wie die Zählung umgangen wird, sehr oft in einfachen Algorithmen und fortgeschrittenen. Die Suche in der Breite funktioniert durch eine konsistente Ansicht der einzelnen Ebenen des Diagramms, beginnend mit dem Knoten der Herkunft, und allmählich von ihm entfernt. Es wird deutlich auf Animation gezeigt.
Um das Beste zu schreiben. BFS Es ist notwendig, mit einer Datenstruktur arbeiten zu können, die es von Anfang und Ende aus zu nehmen ermöglicht und das Diagramm als eine Liste von Nebenitäten (d.h. Zeile) zu halten.
Formale Beschreibung des Algorithmus
(1) Legen Sie die Anzahl der Oberseite, von der die Suche beginnt, in der leeren Zeile.
(2) Holen Sie die Spitze aus der Linie U und markieren Sie es wie in einem separaten Satz verwendet.
(3) Am Ende der Linie, fügen Sie alle Spitzen, die wir durch die Rippen von oben erreichen können. U,und noch nicht markiert.
(4) Ist die Zeile leer, wurden alle Links der Kontaktbox überprüft, andernfalls zurück zu Absatz 2.
Komplexität der Arbeit
Da im schlimmsten Fall der Algorithmus alle Zähl- ' s-Knoten besucht, während der Zählerstand in Form einer Liste von Verbindungen bleibt, ist die temporäre Komplexität des Algorithmus O(|V| + |E|)wenn V - Viele Spitzen der Zählung, a E - Viele Rippen. Mit anderen Worten, der Algorithmus funktioniert für das Schlimmste. Anzahl der Rippen + Anzahl der Spitzen♪

Problem

Einige Dörfer sind durch Straßen miteinander verbunden, die als nicht orientierter Graph dargestellt werden können. Die Eckpunkte dieses Diagramms sind Dörfer und die Kanten sind Straßen zwischen den Dörfern (ein Diagramm kann Zyklen enthalten). Es ist bekannt, dass dasS -DorfKistenhalter.Um ihre kleine Kurzwaren jeden Morgen zu verkaufen, gehen die Korobauer in Dörfer, die noch nicht besucht wurden und zu denen es einen Weg vom aktuellen gibt. Die Artel der Korobeiniker ist immer in Gruppen unterteilt, so dass sie alle Dörfer, die Straßen von der aktuellen haben, an einem Tag durchqueren können.
In wie vielen Tagen werden die Korobayniki alle Dörfer besuchen? Schreiben Sie eine BFS -Funktion, die eine Antwort auf die Aufgabe zurückgibt.

 
Eingabe
Die erste Zeile enthält 3 ganze Zahlen n, m, s (\(1 <= n <= 10^5\), \(0 <= m <= 10^5\), \( 1 <= s <= n\)) - die Anzahl der Dörfer, die Anzahl der Straßen zwischen ihnen und die Nummer des Dorfes, in dem das Korobeiniker-Artel basiert. Die folgenden m Zeilen enthalten jeweils 2 Zahlen u, v(\(1 <= u, v <= n\)) - die Zahlen der beiden Dörfer, zwischen denen eine Straße liegt. Die Indizierung von Dörfern erfolgt mit 1.

Ausgabe
Geben Sie eine Zahl heraus - in wie vielen Tagen werden die Korobeiniker alle Dörfer besuchen.

 

Beispiele
№ Eingabe Ausgabe
1 6 7 1
1 2
1 5
2 3
5 4
3 4
3 6
4 6		 4

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++
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!