{"id":33988,"date":"2024-11-01T09:22:46","date_gmt":"2024-11-01T09:22:46","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33988"},"modified":"2024-11-01T10:54:25","modified_gmt":"2024-11-01T10:54:25","slug":"c-coding-test-course-topological-sorting","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33988\/","title":{"rendered":"C# Coding Test Course, Topological Sorting"},"content":{"rendered":"<article>\n<section>\n<h2>1. What is Topological Sorting?<\/h2>\n<p>\n            Topological sorting is a method of linearly ordering nodes in a directed graph. The main characteristic of this sorting is that all edges in the graph follow the order of the sorted nodes. In other words, if there is an edge from node A to node B, node A must precede node B. Topological sorting, which possesses this property, is mainly used for determining the order of tasks or in scheduling problems.\n        <\/p>\n<p>\n            Topological sorting can only be applied in Directed Acyclic Graphs (DAGs). If a cycle exists, topological sorting cannot be performed, which signifies an impossible state due to the nature of the graph. There are two main methods to implement topological sorting:<br \/>\n            1) DFS (Depth First Search) based method<br \/>\n            2) Kahn&#8217;s algorithm\n        <\/p>\n<\/section>\n<section>\n<h2>2. Problem Description<\/h2>\n<p>\n            The following is a problem that requires the use of topological sorting.\n        <\/p>\n<h3>Problem: Course Completion Order<\/h3>\n<p>\n            You are a college student. You need to complete several courses to graduate. The prerequisites for each course are that other courses must be completed first. Based on this information, print the order in which each course should be completed. If the ordering is not possible, print &#8220;IMPOSSIBLE&#8221;.\n        <\/p>\n<p>\n            Input Format:<br \/>\n            &#8211; The first line contains the number of courses N (1 \u2264 N \u2264 1000) and the number of prerequisites M (0 \u2264 M \u2264 100,000).<br \/>\n            &#8211; The next M lines contain two integers u, v representing the prerequisite relationships. In this case, course u must be completed before course v.\n        <\/p>\n<p>\n            Output Format:<br \/>\n            &#8211; Print the order of course completion, one per line.<br \/>\n            &#8211; If the ordering is not possible, print &#8220;IMPOSSIBLE&#8221;.\n        <\/p>\n<\/section>\n<section>\n<h2>3. Problem Solving Process<\/h2>\n<p>\n            First, we need to understand the number of courses and the prerequisite relationships through input. To do this, we use an adjacency list to represent the graph. We also need to create an array to store the in-degrees of each node. The in-degree represents the number of prerequisites for that node.\n        <\/p>\n<p>\n            1) Graph Construction:<br \/>\n            &#8211; Construct the adjacency list and in-degree array based on the prerequisite relationships given in the input.\n        <\/p>\n<p>\n            2) Topological Sorting Using In-Degree:<br \/>\n            &#8211; Add nodes with an in-degree of 0 to the queue. In this case, the course has no prerequisites, hence can be completed first.<br \/>\n            &#8211; Remove a node from the queue and decrease the in-degree of its connected nodes by 1. If the in-degree becomes 0, add that node to the queue.<br \/>\n            &#8211; Repeat this process to process all nodes. If the number of processed nodes is not equal to the total number of courses, it indicates the presence of a cycle, so &#8220;IMPOSSIBLE&#8221; should be printed.\n        <\/p>\n<\/section>\n<section>\n<h2>4. C# Code Implementation<\/h2>\n<pre>\n<code>\nusing System;\nusing System.Collections.Generic;\n\nclass Program\n{\n    static void Main()\n    {\n        \/\/ Receiving input\n        int N = int.Parse(Console.ReadLine());\n        int M = int.Parse(Console.ReadLine());\n\n        \/\/ Initializing adjacency list and in-degree array\n        List<int>[] graph = new List<int>[N + 1];\n        int[] inDegree = new int[N + 1];\n\n        for (int i = 1; i &lt;= N; i++)\n        {\n            graph[i] = new List<int>();\n        }\n\n        \/\/ Receiving prerequisite relationships\n        for (int i = 0; i &lt; M; i++)\n        {\n            string[] input = Console.ReadLine().Split();\n            int u = int.Parse(input[0]);\n            int v = int.Parse(input[1]);\n\n            graph[u].Add(v);\n            inDegree[v]++;\n        }\n\n        \/\/ Initializing queue and result list\n        Queue<int> queue = new Queue<int>();\n        List<int> result = new List<int>();\n\n        \/\/ Adding nodes with an in-degree of 0 to the queue\n        for (int i = 1; i &lt;= N; i++)\n        {\n            if (inDegree[i] == 0)\n            {\n                queue.Enqueue(i);\n            }\n        }\n\n        \/\/ Topological Sorting\n        while (queue.Count &gt; 0)\n        {\n            int node = queue.Dequeue();\n            result.Add(node);\n\n            foreach (int neighbor in graph[node])\n            {\n                inDegree[neighbor]--;\n                if (inDegree[neighbor] == 0)\n                {\n                    queue.Enqueue(neighbor);\n                }\n            }\n        }\n\n        \/\/ Output result\n        if (result.Count != N)\n        {\n            Console.WriteLine(\"IMPOSSIBLE\");\n        }\n        else\n        {\n            foreach (int course in result)\n            {\n                Console.WriteLine(course);\n            }\n        }\n    }\n}\n<\/int><\/int><\/int><\/int><\/int><\/int><\/int><\/code>\n        <\/pre>\n<p>\n            This code demonstrates how to perform topological sorting based on the number of given courses and prerequisite relationships.<br \/>\n            It allows linear sorting of each course according to the prerequisite relationships in the graph.\n        <\/p>\n<\/section>\n<section>\n<h2>5. Conclusion<\/h2>\n<p>\n            Topological sorting is one of the most important algorithms in graph theory.<br \/>\n            It can be applied in many practical problems and is a topic often covered in programming tests.<br \/>\n            I hope this problem helped you understand how to utilize topological sorting.\n        <\/p>\n<p>\n            Now you have the skills to implement topological sorting using C# and adapt to various problems that require it.<br \/>\n            I encourage you to continue challenging yourself with a variety of problems that necessitate topological sorting.\n        <\/p>\n<\/section>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>1. What is Topological Sorting? Topological sorting is a method of linearly ordering nodes in a directed graph. The main characteristic of this sorting is that all edges in the graph follow the order of the sorted nodes. In other words, if there is an edge from node A to node B, node A must &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33988\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;C# Coding Test Course, Topological Sorting&#8221;<\/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":[90],"tags":[],"class_list":["post-33988","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>C# 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\/33988\/\" \/>\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, Topological Sorting - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"1. What is Topological Sorting? Topological sorting is a method of linearly ordering nodes in a directed graph. The main characteristic of this sorting is that all edges in the graph follow the order of the sorted nodes. In other words, if there is an edge from node A to node B, node A must &hellip; \ub354 \ubcf4\uae30 &quot;C# Coding Test Course, Topological Sorting&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33988\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:22:46+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:54:25+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\/33988\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33988\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C# Coding Test Course, Topological Sorting\",\"datePublished\":\"2024-11-01T09:22:46+00:00\",\"dateModified\":\"2024-11-01T10:54:25+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33988\/\"},\"wordCount\":538,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C# Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33988\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33988\/\",\"name\":\"C# Coding Test Course, Topological Sorting - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:22:46+00:00\",\"dateModified\":\"2024-11-01T10:54:25+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33988\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33988\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33988\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C# 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":"C# 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\/33988\/","og_locale":"ko_KR","og_type":"article","og_title":"C# Coding Test Course, Topological Sorting - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"1. What is Topological Sorting? Topological sorting is a method of linearly ordering nodes in a directed graph. The main characteristic of this sorting is that all edges in the graph follow the order of the sorted nodes. In other words, if there is an edge from node A to node B, node A must &hellip; \ub354 \ubcf4\uae30 \"C# Coding Test Course, Topological Sorting\"","og_url":"https:\/\/atmokpo.com\/w\/33988\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:22:46+00:00","article_modified_time":"2024-11-01T10:54:25+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\/33988\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33988\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C# Coding Test Course, Topological Sorting","datePublished":"2024-11-01T09:22:46+00:00","dateModified":"2024-11-01T10:54:25+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33988\/"},"wordCount":538,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C# Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33988\/","url":"https:\/\/atmokpo.com\/w\/33988\/","name":"C# Coding Test Course, Topological Sorting - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:22:46+00:00","dateModified":"2024-11-01T10:54:25+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33988\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33988\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33988\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C# 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\/33988","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=33988"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33988\/revisions"}],"predecessor-version":[{"id":33989,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33988\/revisions\/33989"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33988"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33988"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33988"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}