Module: Derinlemesine arayın. DFS


Problem

1/12

DFS: Başlangıç ​​(C++)

Theory Click to read/hide

DFS DFS
Önce derinlik araması (DFS), grafiklerdeki ana algoritmalardan biridir. Algoritma O(N + M) şeklinde çalışır.
 
Algoritma
Başlangıç ​​olarak tepeden başlıyoruz, bu tepenin çocuklarını ele alıyoruz ve onları hiç girmemişsek onlardan DFS başlatıyoruz.


Problem

Yönlendirilmemiş bir grafiğin derinliğini başlangıç ​​köşe noktasından S kateden ve tepe noktasından başlayarak tüm köşeleri geçiş sırasına göre çıkaran bir prosedür void dfs (int v) yazın S bir satırda boşlukla ayrılmış.

İlk satır üç sayı içerir N  - grafikteki köşe sayısı, M - kenarların sayısı, S - başlangıç tepe noktası Aşağıdaki M satırlarında 2 değişken Ui ve Vi sağlanır , grafik kenarlarının açıklaması. Girişteki tüm sayılar 1000'i geçmez.

Tüm köşeleri, geçiş sırasına göre  DFS ile çıktılayın.

Yukarıdaki programda g[i][j], i ve j köşeleri arasında bir kenar olduğu anlamına gelir ve kullanılan dizisi ile bu zirveyi ziyaret edip etmediğimizi işaretliyoruz. 

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!