Module: 심층적으로 검색하십시오. DFS


Problem

1/12

DFS: 시작(C++)

Theory Click to read/hide

DFS DFS
깊이 우선 검색(DFS)은 그래프의 주요 알고리즘 중 하나입니다. 알고리즘은 O(N + M)에서 실행됩니다.
 
알고리즘
우선 맨 위부터 시작하여 이 맨 위의 하위 항목을 고려하고 입력한 적이 없는 경우 해당 항목에서 DFS를 시작합니다.


Problem

시작 정점 S에서 무향 그래프의 깊이를 순회하고 정점에서 시작하여 순회 순서로 모든 정점을 출력하는 프로시저 void dfs (int v)를 작성합니다. S는 한 줄에 공백으로 구분됩니다.
<사업부>
첫 번째 줄에는 세 개의 숫자 N  - 그래프의 정점 수, M - 가장자리 수, S - 시작 꼭지점. 다음 M 줄에서 2개의 변수 Ui 및 Vi 제공되는 , 그래프 에지 설명. 입력의 모든 숫자는 1000을 초과하지 않습니다.
<사업부>
DFS 순회 순서대로 모든 정점을 출력합니다.

위의 프로그램에서 g[i][j]는 정점 i와 j 사이에 가장자리가 있음을 의미하며, 배열 used는 이 피크를 방문했는지 여부를 표시합니다. 

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!