Problem

1/6

बीएफएस: शुरुआत (सी++)

Theory Click to read/hide

चौड़ाई पहले खोज (BFS)
BFS (चौड़ाई-पहली खोज, चौड़ाई-पहली खोज) - एक ग्राफ़ ट्रैवर्सल विधि, जिसका उपयोग अक्सर सरल और उन्नत एल्गोरिदम दोनों में किया जाता है। ब्रेड्थ-फर्स्ट सर्च ग्राफ़ के अलग-अलग स्तरों के माध्यम से काम करता है, स्रोत नोड से शुरू होता है और धीरे-धीरे इससे दूर हो जाता है। यह एनीमेशन में स्पष्ट रूप से दिखाया गया है।
सबसे सरल BFS  लिखने के लिए, आपको एक डेटा संरचना के साथ काम करने में सक्षम होने की आवश्यकता है जो आपको शुरुआत से लेने और इसे अंत तक रखने की अनुमति देता है, और स्टोर करने में भी सक्षम है आसन्न सूची के रूप में ग्राफ (यानी कतार के साथ)।
 
एल्गोरिदम का औपचारिक विवरण
1) शुरुआती खाली कतार में उस शीर्ष की संख्या डालें जहां से खोज शुरू होती है।
2) कतार की शुरुआत से शीर्ष U निकालें और इसे एक अलग सरणी में उपयोग के रूप में चिह्नित करें।
3) कतार के अंत में, वे सभी कोने जोड़ें जिन तक हम शीर्ष U, के किनारे का उपयोग करके पहुंच सकते हैं और जिन्हें अभी तक लेबल नहीं किया गया है।
4) यदि कतार खाली है, तो जुड़े हुए ग्राफ़ के सभी नोड्स स्कैन किए गए हैं, अन्यथा चरण 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 < = यू, वी <= एन\)) - दो गांवों की संख्या जिनके बीच एक सड़क है। गांवों को 1 से अनुक्रमित किया जाता है।

छाप
एक ही नंबर प्रिंट करें - सभी गांवों का दौरा करने में फेरीवालों को कितने दिन लगेंगे।

 

उदाहरण
<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड"> <सिर> <वें># <वें>इनपुट <वें>आउटपुट <शरीर> 1 6 7 1
1 2
15
23
5 4
34
36
4 6 4

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>
#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!