Swift Coding Test Course, Find Cities at a Specific Distance

Problem Description

There are N cities, and there are M one-way roads between them.
Each city is represented by an integer from 1 to N. If there is a road from city A to city B,
you can travel from A to B.
Write a program to find all cities that are exactly K distance away.
Ensure that the same city is not printed more than once.

Input Format

    N M K
    A1 B1
    A2 B2
    ...
    Am Bm
    

• N: Number of cities (1 ≤ N ≤ 30000)
• M: Number of roads (1 ≤ M ≤ 200000)
• K: Distance to find (0 ≤ K ≤ 30000)
• A1, B1: Road from city A to city B

Output Format

    Print the city numbers that are K distance away in ascending order.
    If there are no such cities, print -1.
    

Example

Input

    4 4 2
    1 2
    1 3
    2 4
    3 4
    

Output

    4
    

Approach to Solution

This problem can be solved using graph traversal (especially Breadth-First Search BFS).
The given cities can be modeled as nodes, and the roads as edges.
A BFS is performed to find the cities that reach a distance of K.

Overview of BFS Algorithm

BFS works by exploring all adjacent nodes from the starting node, and once
that is complete, it explores the next level of nodes. This method is
suitable for shortest path problems.

Implementation Details

Below is the code that finds cities at a specific distance using BFS in Swift.

    import Foundation

    struct City {
        var number: Int
        var distance: Int
    }

    func findCitiesAtDistanceN(n: Int, roads: [(Int, Int)], k: Int) -> [Int] {
        // Create adjacency list
        var graph = [[Int]](repeating: [Int](), count: n + 1)
        for road in roads {
            let a = road.0
            let b = road.1
            graph[a].append(b)
        }

        // Initialize BFS
        var queue = [City]()
        var distances = Array(repeating: -1, count: n + 1)
        distances[1] = 0 // Assume the starting city is 1
        queue.append(City(number: 1, distance: 0))

        while !queue.isEmpty {
            let current = queue.removeFirst()
            let currentDistance = current.distance
            for neighbor in graph[current.number] {
                if distances[neighbor] == -1 { // If not visited yet
                    distances[neighbor] = currentDistance + 1
                    queue.append(City(number: neighbor, distance: distances[neighbor]!))
                }
            }
        }

        // Find cities at distance K
        let result = distances.enumerated().compactMap { index, distance in
            distance == k ? index : nil
        }.sorted()

        return result.isEmpty ? [-1] : result
    }

    // Example input
    let roads = [(1, 2), (1, 3), (2, 4), (3, 4)]
    let result = findCitiesAtDistanceN(n: 4, roads: roads, k: 2)
    
    print(result) // Output: [4]
    

Code Explanation

In the above code, we first create an adjacency list.
Each city stores its connected neighboring cities as an array.
Then, we perform BFS to calculate the distances for each city.
Finally, we find and print the cities at distance K.

Complexity Analysis

Since we visit every node in the graph,
the time complexity is O(N + M).
The space complexity is also O(N + M).

Conclusion

In this lecture, we addressed the problem of finding cities at a specific distance.
It can be efficiently solved using BFS,
requiring careful implementation. By mastering this algorithm,
you can establish a solid foundation for solving complex graph
and road problems.