Input Format<\/strong><\/p>\nThe first line contains the number of nodes N (1 \u2264 N \u2264 10^5) and the number of edges M (1 \u2264 M \u2264 2 * 10^5).\nThe next M lines represent the two nodes u, v (1 \u2264 u, v \u2264 N) of each edge.\nThe last line gives the starting node S.<\/pre>\nOutput Format<\/strong><\/p>\nOutput the shortest distance to each node, separated by spaces.\nIf a node is not connected, output -1.<\/pre>\nSolution Process<\/h2>\n
Let’s take a step-by-step look at how to solve the problem using BFS.<\/p>\n
Step 1: Graph Representation<\/h3>\n
We will use an adjacency list to represent the graph. The adjacency list stores the other nodes connected to each node in a list format. This allows efficient memory usage.<\/p>\n
Step 2: Implementing BFS<\/h3>\n
BFS explores adjacent nodes using a queue. The exploration order is as follows:<\/p>\n
\n- Insert the starting node into the queue and initialize the distance to 0.<\/li>\n
- Remove a node from the queue and check all nodes adjacent to that node.<\/li>\n
- If the explored node is unvisited, set its distance to the current node’s distance + 1 and insert it into the queue.<\/li>\n
- Repeat this process until the queue is empty.<\/li>\n<\/ol>\n
Step 3: Writing the Code<\/h3>\n
Now, based on the above process, let’s write the C++ code.<\/p>\n
\n
\n#include \n#include \n#include \n#include \n\nusing namespace std;\n\nconst int MAX_N = 100000;\nvector graph[MAX_N + 1];\nint dist[MAX_N + 1];\n\nvoid bfs(int start, int n) {\n queue q;\n fill(dist, dist + n + 1, -1); \/\/ Initialize distances\n dist[start] = 0; \/\/ Set distance for the start node\n q.push(start); \/\/ Insert start node into the queue\n\n while(!q.empty()) {\n int current = q.front();\n q.pop();\n \n for(int neighbor : graph[current]) {\n if(dist[neighbor] == -1) { \/\/ Unvisited node\n dist[neighbor] = dist[current] + 1;\n q.push(neighbor);\n }\n }\n }\n}\n\nint main() {\n int N, M, S;\n cin >> N >> M;\n \n for(int i = 0; i < M; ++i) {\n int u, v;\n cin >> u >> v;\n graph[u].push_back(v); \/\/ Add undirected edge\n graph[v].push_back(u);\n }\n cin >> S;\n\n bfs(S, N); \/\/ Call BFS\n\n for(int i = 1; i <= N; ++i) {\n cout << dist[i] << \" \"; \/\/ Output distances\n }\n cout << endl;\n\n return 0;\n}\n<\/code><\/pre>\n<\/div>\nStep 4: Executing the Code and Results<\/h2>\n
By executing the above code, we calculate and output the shortest distance from the starting node S to each node. For example, if the following input is given:<\/p>\n
Input Example:<\/strong><\/p>\n\n6 7\n1 2\n1 3\n2 4\n3 4\n4 5\n4 6\n5 6\n1\n<\/pre>\nOutput Example:<\/strong><\/p>\n\n0 1 1 2 3 2 \n<\/pre>\nStep 5: Conclusion<\/h2>\n
In this lecture, we explored the Breadth-First Search (BFS) algorithm, which often appears in C++ coding tests. BFS is useful for solving shortest path problems and can be applied to various challenges. By thoroughly understanding and utilizing this algorithm, you can achieve good results in coding tests.<\/p>\n
I hope this lecture has been helpful for your job preparation. Thank you!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Hello everyone! Today, I will explain the Breadth-First Search (BFS) algorithm, which often appears in coding tests. In this lecture, we will explore the fundamental concepts of BFS and solve a sample algorithm problem using it. What is BFS? Breadth-First Search (BFS) is one of the algorithms used to explore nodes in graph theory. BFS … \ub354 \ubcf4\uae30 “C++ Coding Test Course, Breadth-First Search”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[111],"tags":[],"class_list":["post-34160","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials-2"],"yoast_head":"\nC++ Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34160\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello everyone! Today, I will explain the Breadth-First Search (BFS) algorithm, which often appears in coding tests. In this lecture, we will explore the fundamental concepts of BFS and solve a sample algorithm problem using it. What is BFS? Breadth-First Search (BFS) is one of the algorithms used to explore nodes in graph theory. BFS … \ub354 \ubcf4\uae30 "C++ Coding Test Course, Breadth-First Search"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34160\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:24:57+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:58:22+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34160\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34160\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Breadth-First Search\",\"datePublished\":\"2024-11-01T09:24:57+00:00\",\"dateModified\":\"2024-11-01T10:58:22+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34160\/\"},\"wordCount\":444,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34160\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34160\/\",\"name\":\"C++ Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:24:57+00:00\",\"dateModified\":\"2024-11-01T10:58:22+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34160\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34160\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34160\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ Coding Test Course, Breadth-First Search\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C++ Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34160\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello everyone! Today, I will explain the Breadth-First Search (BFS) algorithm, which often appears in coding tests. In this lecture, we will explore the fundamental concepts of BFS and solve a sample algorithm problem using it. What is BFS? Breadth-First Search (BFS) is one of the algorithms used to explore nodes in graph theory. BFS … \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Breadth-First Search\"","og_url":"https:\/\/atmokpo.com\/w\/34160\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:24:57+00:00","article_modified_time":"2024-11-01T10:58:22+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34160\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34160\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Breadth-First Search","datePublished":"2024-11-01T09:24:57+00:00","dateModified":"2024-11-01T10:58:22+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34160\/"},"wordCount":444,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34160\/","url":"https:\/\/atmokpo.com\/w\/34160\/","name":"C++ Coding Test Course, Breadth-First Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:24:57+00:00","dateModified":"2024-11-01T10:58:22+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34160\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34160\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34160\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ Coding Test Course, Breadth-First Search"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34160","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34160"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34160\/revisions"}],"predecessor-version":[{"id":34161,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34160\/revisions\/34161"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}