Java Coding Test Course, Finding the Order of Building

Problem Description

You are planning to construct several buildings in a city. Each building has an order based on its dependencies with one another. In other words, if building A must be constructed before building B, then the dependency is represented as A -> B. You need to solve the problem of determining the construction order of all buildings according to these rules.

Below is the number of buildings N and the dependency information given as input. You need to output the construction order of all buildings.
For example, let’s assume the following dependencies are given:

            5 4
            2 1
            3 1
            4 2
            5 3
            

This input indicates that there are 5 buildings and the following dependencies exist.
Building 1 must be constructed after building 2, building 1 after building 3, building 2 after building 4, and building 3 after building 5.
In this case, a possible construction order of the buildings could be:

            1, 2, 3, 4, 5 or 1, 2, 3, 5, 4, etc.
            

Strategy for Problem Solving

To solve this problem, we can utilize the concept of topological sorting from graph theory. Topological sorting is the act of arranging all vertices (nodes) in a directed graph according to the direction of the edges. In this case, if there is an edge A -> B, A must come before B.

The main steps of the algorithm are as follows:

1. Implement the graph in the form of an adjacency list.
2. Calculate the in-degree of each node.
3. Add the nodes with an in-degree of 0 to a queue to start processing.
4. While removing nodes from the queue, record the order and decrease the in-degree of the other connected nodes. If any node’s in-degree becomes 0, add it back to the queue.
5. Repeat until all nodes are processed.

Java Implementation Code

Based on the algorithm described above, let’s implement the code in Java. Below is the Java code that performs topological sorting.

                
public class BuildingOrder {
    import java.util.*;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Receiving input for buildings and dependencies
        int N = scanner.nextInt(); // Number of buildings
        int M = scanner.nextInt(); // Number of dependencies
        
        List> graph = new ArrayList<>();
        int[] inDegree = new int[N + 1]; // In-degree
        
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < M; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph.get(a).add(b);
            inDegree[b]++;
        }
        
        // Implementing the process to perform topological sorting
        StringBuilder result = new StringBuilder();
        Queue queue = new LinkedList<>();

        // Adding nodes with in-degree of 0 to the queue
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.append(current).append(" ");

            for (int neighbor : graph.get(current)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // Outputting the result
        System.out.println("Construction order of buildings: ");
        System.out.println(result.toString().trim());
        scanner.close();
    }
}
                
            

The above code first receives the number of buildings and their dependencies, initializes the graph and in-degrees based on this input, and then determines the construction order through topological sorting and prints it.

Input and Output Examples

Example Input

            5 4
            2 1
            3 1
            4 2
            5 3
            

Example Output

            Construction order of buildings: 
            1 2 3 4 5 or 1 2 3 5 4
            

Advanced Learning

The topological sorting algorithm can be used in many real-world situations. For example, it is useful for project schedule management, grammar parsing in compilers, and solving problems with precedence relationships among multiple tasks. Understanding and effectively utilizing such algorithms can greatly aid in problem-solving not only for coding tests but also across various fields.

Practice Problems:

1. Use topological sorting to determine the construction order for the following graph.

2. Implement the following dependencies and visualize the graph to think about what issues might arise.