\n There are N cities, and there are M one-way roads between them.
\n Each city is represented by an integer from 1 to N. If there is a road from city A to city B,
\n you can travel from A to B.
\n Write a program to find all cities that are exactly K distance away.
\n Ensure that the same city is not printed more than once.\n <\/p>\n
\n N M K\n A1 B1\n A2 B2\n ...\n Am Bm\n <\/pre>\n
\n Print the city numbers that are K distance away in ascending order.\n If there are no such cities, print -1.\n <\/pre>\nExample<\/h2>\n
Input<\/h3>\n
\n 4 4 2\n 1 2\n 1 3\n 2 4\n 3 4\n <\/pre>\nOutput<\/h3>\n
\n 4\n <\/pre>\nApproach to Solution<\/h2>\n
\n This problem can be solved using graph traversal (especially Breadth-First Search BFS).
\n The given cities can be modeled as nodes, and the roads as edges.
\n A BFS is performed to find the cities that reach a distance of K.\n <\/p>\nOverview of BFS Algorithm<\/h3>\n
\n BFS works by exploring all adjacent nodes from the starting node, and once
\n that is complete, it explores the next level of nodes. This method is
\n suitable for shortest path problems.\n <\/p>\nImplementation Details<\/h2>\n
Below is the code that finds cities at a specific distance using BFS in Swift.<\/p>\n
\n import Foundation\n\n struct City {\n var number: Int\n var distance: Int\n }\n\n func findCitiesAtDistanceN(n: Int, roads: [(Int, Int)], k: Int) -> [Int] {\n \/\/ Create adjacency list\n var graph = [[Int]](repeating: [Int](), count: n + 1)\n for road in roads {\n let a = road.0\n let b = road.1\n graph[a].append(b)\n }\n\n \/\/ Initialize BFS\n var queue = [City]()\n var distances = Array(repeating: -1, count: n + 1)\n distances[1] = 0 \/\/ Assume the starting city is 1\n queue.append(City(number: 1, distance: 0))\n\n while !queue.isEmpty {\n let current = queue.removeFirst()\n let currentDistance = current.distance\n for neighbor in graph[current.number] {\n if distances[neighbor] == -1 { \/\/ If not visited yet\n distances[neighbor] = currentDistance + 1\n queue.append(City(number: neighbor, distance: distances[neighbor]!))\n }\n }\n }\n\n \/\/ Find cities at distance K\n let result = distances.enumerated().compactMap { index, distance in\n distance == k ? index : nil\n }.sorted()\n\n return result.isEmpty ? [-1] : result\n }\n\n \/\/ Example input\n let roads = [(1, 2), (1, 3), (2, 4), (3, 4)]\n let result = findCitiesAtDistanceN(n: 4, roads: roads, k: 2)\n \n print(result) \/\/ Output: [4]\n <\/code><\/pre>\nCode Explanation<\/h2>\n
\n In the above code, we first create an adjacency list.
\n Each city stores its connected neighboring cities as an array.
\n Then, we perform BFS to calculate the distances for each city.
\n Finally, we find and print the cities at distance K.\n <\/p>\nComplexity Analysis<\/h2>\n
\n Since we visit every node in the graph,
\n the time complexity is O(N + M).
\n The space complexity is also O(N + M).\n <\/p>\nConclusion<\/h2>\n
\n In this lecture, we addressed the problem of finding cities at a specific distance.
\n It can be efficiently solved using BFS,
\n requiring careful implementation. By mastering this algorithm,
\n you can establish a solid foundation for solving complex graph
\n and road problems.\n <\/p>\n<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"