Module: Suche in die Tiefe. DFS


Problem

1/12

DFS: Anfang (C++)

Theory Click to read/hide

Suche tief.DFS
Erkennung tief.DFS) ist einer der Hauptalgorithmen auf den Zählungen. Algorithm arbeitet für O(N + M)♪
Algorithmen
Für Anfänger beginnen wir von oben, schauen uns die Kinder dieses Tops an, und wenn wir nie reingekommen sind, fangen wir mit ihnen an. DFS♪


Problem

Schreiben Sie das Verfahren void dfs (int v)die in die Tiefe der unorientierten Reihe von der ersten Spitze geht S und dreht alle Spitzen um, von oben. S durch einen Spalt in einer Linie.

In der ersten Zeile drei Zahlen N- Anzahl der Spitzen in der Zählung, M - Anzahl der Rippen, S - Ein Ausgangspunkt. Nächste M 2 variable Zeilen Ui und Vieine Beschreibung der Zählrippe. Alle Einträge überschreiten 1.000 nicht.

Holen Sie alle Tops aus dem Algorithmus Bypass.DFS♪

Im vorliegenden Programm,g[i][j] zeigt, dass zwischen den Oberseiten i und j Da ist eine Rippe, sie ist in der Masse. used Wir werden sehen, ob wir hier sind.

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>

using namespace std;

vector < vector < int > > g;
vector < bool > used;

void dfs(int v) 
{            
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m, s, u, v;

	cin >> n >> m >> s;

	g.resize(n);
	used.resize(n);

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		g[u - 1].push_back(v - 1);
		g[v - 1].push_back(u - 1);
	}

	dfs(s - 1);
	return 0;
}

     

Program check result

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