The next M lines contain two integers in the form of ‘A B’, meaning that to finish course ‘A’, course ‘B’ must be completed first.<\/li>\n<\/ul>\nOutput Format<\/h3>\n
Output the order of course completion in a single line separated by spaces. If there are multiple valid orders of completion, only output the lexicographically smallest course order.<\/p>\n
Solution Process<\/h2>\n1. Understanding the Problem<\/h3>\n
To solve the problem, we must first understand the concept of Topological Sort. In the graph, vertices represent courses, and edges represent prerequisites. We can construct a directed graph that indicates which courses must be completed in order to take others.<\/p>\n
2. Constructing the Graph<\/h3>\n
Based on the given courses and prerequisites, construct the graph. Each course becomes a node, and prerequisites are represented as directed edges.<\/p>\n
val graph = mutableMapOf>()\nval inDegree = IntArray(N + 1) \/\/ Stores the in-degree of each course\n<\/int,><\/code><\/pre>\n3. Calculating In-Degree<\/h3>\n
Calculate the in-degree of each course. The in-degree represents the number of courses that must be completed before reaching that course.<\/p>\n
for (i in 0 until M) {\n val a = readLine()!!.split(' ').map { it.toInt() }\n graph.getOrPut(a[1]) { mutableListOf() }.add(a[0])\n inDegree[a[0]]++\n}\n<\/code><\/pre>\n4. Implementing Topological Sort Algorithm<\/h3>\n
Topological Sort can be implemented using BFS. Starting from nodes with an in-degree of 0, visit these nodes in order while decrementing their in-degrees. If any node’s in-degree becomes 0 during this process, add it to the queue.<\/p>\n
fun topologicalSort(N: Int): List {\n val result = mutableListOf()\n val queue: Queue = LinkedList()\n\n \/\/ Add nodes with in-degree of 0 to the queue\n for (i in 1..N) {\n if (inDegree[i] == 0) {\n queue.add(i)\n }\n }\n\n while (queue.isNotEmpty()) {\n \/\/ Remove vertex from queue for lexicographical sorting\n val current = queue.poll()\n result.add(current)\n\n \/\/ Process the outgoing edges from the current vertex\n for (next in graph[current] ?: listOf()) {\n inDegree[next]--\n if (inDegree[next] == 0) {\n queue.add(next)\n }\n }\n }\n\n return result\n}\n<\/int><\/int><\/int><\/code><\/pre>\n5. Final Code<\/h3>\n
The final code including the Topological Sort functionality is as follows.<\/p>\n
fun main() {\n val (N, M) = readLine()!!.split(' ').map { it.toInt() }\n\n val graph = mutableMapOf>()\n val inDegree = IntArray(N + 1)\n\n \/\/ Initialize graph and in-degrees\n for (i in 0 until M) {\n val (a, b) = readLine()!!.split(' ').map { it.toInt() }\n graph.getOrPut(b) { mutableListOf() }.add(a)\n inDegree[a]++\n }\n\n \/\/ Perform Topological Sort\n val result = topologicalSort(N)\n \n \/\/ Output the result\n println(result.joinToString(\" \"))\n}\n<\/int,><\/code><\/pre>\nConclusion<\/h2>\n
Topological Sort is a very useful algorithm for solving various graph problems. It shines especially in situations where dependencies must be taken into account, such as in course prerequisite problems. In this lesson, we examined the basic concepts of Topological Sort and followed a step-by-step problem-solving process. I hope you continue to enhance your Kotlin skills through various algorithm problems.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Overview Topological Sort is an algorithm for linearly ordering vertices in a directed graph. This algorithm is mainly used for problems that express dependencies of tasks. For example, it is useful for solving various problems such as course prerequisites, task scheduling, etc. Problem Description The following is a problem utilizing Topological Sort. Problem: Course Prerequisite … \ub354 \ubcf4\uae30 “kotlin coding test course, topological sorting”<\/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":[106],"tags":[],"class_list":["post-35090","post","type-post","status-publish","format-standard","hentry","category----en"],"yoast_head":"\nkotlin coding test course, topological sorting - \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\/35090\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"kotlin coding test course, topological sorting - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Overview Topological Sort is an algorithm for linearly ordering vertices in a directed graph. This algorithm is mainly used for problems that express dependencies of tasks. For example, it is useful for solving various problems such as course prerequisites, task scheduling, etc. Problem Description The following is a problem utilizing Topological Sort. Problem: Course Prerequisite … \ub354 \ubcf4\uae30 "kotlin coding test course, topological sorting"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/35090\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:35:24+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:45:01+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=\"1\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/35090\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35090\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"kotlin coding test course, topological sorting\",\"datePublished\":\"2024-11-01T09:35:24+00:00\",\"dateModified\":\"2024-11-01T11:45:01+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35090\/\"},\"wordCount\":405,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/35090\/\",\"url\":\"https:\/\/atmokpo.com\/w\/35090\/\",\"name\":\"kotlin coding test course, topological sorting - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:35:24+00:00\",\"dateModified\":\"2024-11-01T11:45:01+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35090\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/35090\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/35090\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"kotlin coding test course, topological sorting\"}]},{\"@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":"kotlin coding test course, topological sorting - \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\/35090\/","og_locale":"ko_KR","og_type":"article","og_title":"kotlin coding test course, topological sorting - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Overview Topological Sort is an algorithm for linearly ordering vertices in a directed graph. This algorithm is mainly used for problems that express dependencies of tasks. For example, it is useful for solving various problems such as course prerequisites, task scheduling, etc. Problem Description The following is a problem utilizing Topological Sort. Problem: Course Prerequisite … \ub354 \ubcf4\uae30 \"kotlin coding test course, topological sorting\"","og_url":"https:\/\/atmokpo.com\/w\/35090\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:35:24+00:00","article_modified_time":"2024-11-01T11:45:01+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":"1\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/35090\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/35090\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"kotlin coding test course, topological sorting","datePublished":"2024-11-01T09:35:24+00:00","dateModified":"2024-11-01T11:45:01+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/35090\/"},"wordCount":405,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/35090\/","url":"https:\/\/atmokpo.com\/w\/35090\/","name":"kotlin coding test course, topological sorting - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:35:24+00:00","dateModified":"2024-11-01T11:45:01+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/35090\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/35090\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/35090\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"kotlin coding test course, topological sorting"}]},{"@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\/35090","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=35090"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35090\/revisions"}],"predecessor-version":[{"id":35091,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35090\/revisions\/35091"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=35090"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=35090"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=35090"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}