Java Coding Test Course, Finding Cities at a Specific Distance

Hello, everyone! Today, we will be tackling algorithm problems for job preparation using Java. The topic this time is “Finding Cities at a Specific Distance,” utilizing graph theory and the BFS (Breadth-First Search) algorithm. We will delve deep into the fundamental concepts of algorithms and how to effectively use Java’s useful data structures while solving this problem.

Problem Description

The given cities are interconnected by roads, and each city is marked with a number. The task is to find and return all cities that can be reached by traveling a specific distance K starting from city number 1. Thus, the input consists of the number of cities N, the number of roads M, the starting city X, and the target distance K, and the output should be the city numbers sorted in ascending order.

Input

• First line: Number of cities N (1 ≤ N ≤ 30000), number of roads M (1 ≤ M ≤ 200000)
• Second line: Starting city number X (1 ≤ X ≤ N) and target distance K (0 ≤ K ≤ 30000)
• Next M lines: Two connected cities A, B (1 ≤ A, B ≤ N, A ≠ B)

Output

Print the numbers of the cities that can be reached at the target distance K in ascending order. If there are no reachable cities, print -1.

Solution Approach

To solve this problem, we need to construct a graph and use the BFS algorithm to find the cities reachable by the given distance K. BFS is suitable for this as it visits all vertices of the graph in level order, which helps in reaching cities at a specific distance.

Step 1: Graph Representation

We use an adjacency list to represent the road relationships between cities. In Java, we can utilize ArrayList to store adjacent cities for each city. This minimizes memory use and makes it easy to manage the relationships between cities.

Step 2: Implementing BFS

To implement BFS, we use a queue to store the current city and the current distance, continuing the search until this distance reaches K. Care should be taken not to revisit cities that have already been visited during the search process. Additionally, we must compare the current distance accurately with K.

Step 3: Output the Results

After collecting the cities that reached the target distance K, we sort them in ascending order and print them. If no city was reachable, we print -1.

Java Code Example

import java.util.*;

public class SpecificDistanceCity {
    static ArrayList[] graph;
    static boolean[] visited;
    static int[] distance;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // Number of cities
        int M = sc.nextInt(); // Number of roads
        int X = sc.nextInt(); // Starting city
        int K = sc.nextInt(); // Target distance

        // Initialize the graph
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // Input road information
        for (int i = 0; i < M; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            graph[A].add(B);
        }

        // Output the results
        List result = bfs(X, K);
        if (result.isEmpty()) {
            System.out.println(-1);
        } else {
            Collections.sort(result);
            for (int city : result) {
                System.out.println(city);
            }
        }

        sc.close();
    }

    private static List bfs(int start, int targetDistance) {
        List reachableCities = new ArrayList<>();
        Queue queue = new LinkedList<>(); // City and current distance
        visited = new boolean[graph.length];
        distance = new int[graph.length];

        queue.offer(new int[]{start, 0}); // (city, distance)
        visited[start] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int currentCity = current[0];
            int currentDistance = current[1];

            // Add city when reaching target distance
            if (currentDistance == targetDistance) {
                reachableCities.add(currentCity);
            }

            // Move to the next distance
            for (int neighbor : graph[currentCity]) {
                if (!visited[neighbor] && currentDistance + 1 <= targetDistance) {
                    visited[neighbor] = true;
                    queue.offer(new int[]{neighbor, currentDistance + 1});
                }
            }
        }

        return reachableCities;
    }
}

Code Explanation

The code above can be divided into three main parts. The main function initializes the graph and inputs the road information, then explores reachable cities using BFS. The BFS function uses a queue to manage the current city and distance and adds the city to the result list when it reaches the target. After all BFS explorations are completed, it sorts and outputs the reachable cities.

Try It Yourself

Now it’s your turn to run the code. Test with various input data to verify if the desired output is achieved. Additionally, try adding comments or modifying conditions in different parts of the code to experiment with its functionality. This will deepen your understanding of the algorithm.

Conclusion

Through this lecture, we learned the basic BFS algorithm and how to implement graphs to solve the problem of finding cities at a specific distance. As employment is the goal, I hope you solve many of these problems and build your skills. In the next lecture, we will tackle a more challenging topic. Thank you!