C++ Coding Test Course, Finding Building Order

Problem Description

A city consists of several buildings, each with a unique number. There are directed roads between the buildings.
The problem is to determine the construction order of these buildings based on specific rules that must be followed.

The construction order of all buildings is determined by the given conditions. This problem can be represented
as a Topological Sort problem. The goal is to calculate and output the desired order of buildings based on the
given rules.

Input Format

The first line contains the number of buildings N and the number of roads M. (1 ≤ N ≤ 10^6, 0 ≤ M ≤ 10^6)
The next M lines contain the information about the roads, where two integers A and B indicate that building A
must be constructed before building B.

Output Format

Output the construction order of the buildings in a single line. If it is impossible to determine the construction order, output ‘0’.

Example

Input

    4 2
    1 2
    2 3
    

Output

    1 2 3 4
    

Approach

To solve this problem, we can consider two methods:
1. Using DFS (Depth-First Search)
2. Using Kahn’s algorithm

The topological sort problem involves finding a possible order of buildings in a directed graph without cycles.
If a cycle exists, the requirements of the problem cannot be satisfied, so a check for cycles is necessary.

1. Method Using DFS

We can perform topological sorting by exploring the graph with DFS, visiting each node. The key of this method
is to add a node to the stack when all of its child nodes have been visited.

2. Kahn’s Algorithm

Kahn’s algorithm uses the in-degree of each node to perform topological sorting. This algorithm includes the following steps:

1. Calculate the in-degrees of the graph.
2. Add nodes with an in-degree of 0 to the queue.
3. Remove nodes from the queue one by one, outputting them, and decrease the in-degrees of all connected nodes.
   If a node’s in-degree becomes 0, add it to the queue.
4. Repeat this process. If all nodes have been visited, we have successfully performed topological sorting
   without cycles.

Implementation

Now, let’s implement the code to solve the problem using the Kahn’s algorithm described above.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void topologicalSort(int N, vector>& graph, vector& inDegree) {
    queue q;
    vector result;

    // Add nodes with in-degree 0 to the queue
    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        result.push_back(current);

        // Decrease the in-degree of all nodes connected to the current node
        for (int neighbor : graph[current]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // Output the result
    if (result.size() == N) {
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << " ";
        }
        cout << endl;
    } else {
        cout << "0" << endl; // If a cycle exists
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector> graph(N + 1);
    vector inDegree(N + 1, 0);

    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B; // A -> B
        graph[A].push_back(B);
        inDegree[B]++;
    }

    topologicalSort(N, graph, inDegree);

    return 0;
}
    

Conclusion

The topological sorting problem is one of the types of algorithm problems that can commonly be encountered,
especially when determining the work order of a project. In this tutorial, we solved the problem of finding the
building order using Kahn’s algorithm. There are various variations of this problem, so to build your skills in
actual coding tests, it is recommended to solve a variety of problems.

Great job! I hope this has been helpful in your preparation for coding tests.