Module: BFS - Genişlik Yürüyüşü


Problem

1/6

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

Theory Click to read/hide

Genişlik Öncelikli Arama (BFS)
BFS (genişlik öncelikli arama, öncelikli arama) - hem basit hem de gelişmiş algoritmalarda sıklıkla kullanılan bir grafik çaprazlama yöntemi. Genişlik Öncelikli Arama, kaynak düğümden başlayarak ve kademeli olarak ondan uzaklaşarak grafiğin bireysel seviyeleri arasında adım atarak çalışır. Bu, animasyonda açıkça gösterilmiştir.
En basit BFS 'i yazmak için baştan alıp sonuna kadar götürebileceğiniz bir veri yapısı ile çalışabilmeniz ve ayrıca depolayabilmeniz gerekir. bitişiklik listesi biçimindeki grafik (yani bir kuyruk ile).
 
Algoritmanın resmi açıklaması
1) Aramanın başladığı köşe numarasını başlangıçta boş olan kuyruğa yerleştirin.
2) Kuyruğun başından U tepe noktasını çıkarın ve ayrı bir dizide kullanılmış olarak işaretleyin.
3) Kuyruğun sonunda, U, köşesinden kenarı kullanarak ulaşabildiğimiz ve henüz etiketlenmemiş tüm köşeleri ekleyin.
4) Kuyruk boşsa, bağlı grafiğin tüm düğümleri taranmıştır, aksi halde 2. adıma dönün.
 
Karmaşıklık
Algoritma grafiğin tüm düğümlerini en kötü durumda ziyaret ettiğinden, grafiği bitişik listeler olarak saklarken, algoritmanın zaman karmaşıklığı O(|V| + |E|) şeklindedir. , burada V grafik tepe noktaları kümesidir ve E kenarlar kümesidir. Başka bir deyişle, algoritma sayı için en kötü durumda çalışır kenar sayısı + köşe sayısı.

 

Problem

Bazı köyler, yönsüz bir grafik olarak temsil edilebilecek yollarla birbirine bağlıdır. Bu grafiğin köşeleri köyler ve kenarları köyler arasındaki yollar (grafik döngüler içerebilir). Köyde S bir artel Seyyar satıcılar. Her sabah seyyar satıcılar, küçük tuhafiyelerini satmak için henüz gidilmemiş ve şimdiki yoldan yol bulunan köylere giderler. Seyyar satıcılar arteli, mevcut köyden yolu olan bütün köyleri bir günde dolaşsınlar diye hep gruplara ayrılır.
Seyyar satıcılar bütün köyleri kaç günde ziyaret ederler? Yanıtı göreve döndürecek bir BFS işlevi yazın.

 
Giriş
İlk satır 3 tam sayı içerir n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - köy sayısı, aralarındaki yol sayısı ve seyyar satıcı çetesinin bulunduğu köyün numarası.  ;Aşağıdaki m< /code> satırlarının her biri 2 sayı içerir u, v(\(1 < = u, v <= n\ )) - aralarında yol bulunan iki köyün sayısı. Köyler 1 ile dizine eklenir.

Künye
Tek bir sayı yazdırın - seyyar satıcıların tüm köyleri ziyaret etmesi kaç gün sürer.

 

Örnekler

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++
# Girdi Çıktı
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!