Module: BFS - 폭 넓은 산책


Problem

1/6

BFS: 시작(C++)

Theory Click to read/hide

폭 우선 검색(BFS)
BFS (breadth-first search,breadth-first search) - 간단한 알고리즘과 고급 알고리즘 모두에서 매우 자주 사용되는 그래프 순회 방법입니다. Breadth-First Search는 소스 노드에서 시작하여 점진적으로 멀어지는 그래프의 개별 수준을 통해 작동합니다. 이것은 애니메이션에서 명확하게 보여집니다.
가장 간단한 BFS 를 작성하려면 처음부터 끝까지 가져와 저장할 수 있는 데이터 구조로 작업할 수 있어야 합니다. 인접 목록 형식의 그래프(예: 대기열 포함).
 
알고리즘에 대한 공식적인 설명
1) 검색이 시작되는 꼭지점의 번호를 초기 빈 큐에 배치합니다.
2) 큐의 시작 부분에서 정점 U를 추출하고 별도의 배열에서 사용된 것으로 표시합니다.
3) 대기열의 끝에서 정점 U,의 가장자리를 사용하여 도달할 수 있고 아직 레이블이 지정되지 않은 모든 정점을 추가합니다.
4) Queue가 비어 있으면 연결된 그래프의 모든 노드를 스캔한 것이며 그렇지 않으면 2단계로 돌아갑니다.
 
복잡성
알고리즘은 최악의 경우 그래프의 모든 노드를 방문하므로 그래프를 인접 목록으로 저장할 때 알고리즘의 시간 복잡도는 O(|V| + |E|) 여기서 V는 그래프 정점 집합이고 E는 가장자리 집합입니다. 즉, 알고리즘은 숫자에 대해 최악의 경우에 작동합니다. 모서리 수 + 정점 수.

 

Problem

일부 마을은 도로로 연결되어 있으며 방향이 없는 그래프로 나타낼 수 있습니다. 이 그래프의 정점은 마을이고 가장자리는 마을 사이의 도로입니다(그래프에는 주기가 포함될 수 있음). 마을에서 S artel 행상인. 매일 아침, 행상인은 작은 잡화를 팔기 위해 아직 방문하지 않은 마을과 현재 마을에서 길이 있는 마을로 이동합니다. 행상인의 아텔은 항상 그룹으로 나뉘어 현재 마을에서 도로가 있는 모든 마을을 하루에 돌아다닐 수 있습니다.
행상인들이 모든 마을을 방문하는 데 며칠이 걸립니까? 작업에 대한 답을 반환하는 BFS 함수를 작성하세요.

 
입력
첫 번째 줄에는 3개의 정수 n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - 마을 수, 마을 사이의 도로 수, 행상인 갱단이 기반을 두고 있는 마을 수.  ;다음 m 줄에는 각 u, v(\(1 < = u, v <= n\ )) - 도로가 있는 두 마을의 수. 마을은 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!