Cody

Problem 45503. Place wastewater treatment processes in the correct order

There are many technologies for treating wastewater. For example, grit chambers are used to remove heavy solids, filtration is used to remove smaller solids, chemical oxidation disinfects the water from bacteria, and so on. By performing these steps one after the other, it is possible to recycle sewage water back to nature.

However, the steps must be performed in the correct order, i.e. some technologies must be performed before others. In this problem, we will label these technologies as 1, 2, ... N. You are then given a [ K x 2] matrix called P, which is a list of constraints to be read as follows:

"Technology P( i, 1) must be performed before P( i, 2)," for all rows i.

Your task is to list all N technologies from left to right in the order that they should be performed, that is, without violating any constraint. If there are multiple possible orderings, choose the one in which the technologies with the smaller labels come earlier. Your output will be essential for designing the sequence of steps in a wastewater treatment plant.

Consider the following example:

N = 4; P = [1 2;
            3 4];
Possible orderings: [1 2 3 4], [1 3 2 4], [1 3 4 2],
                    [3 1 2 4], [3 1 4 2], [3 4 1 2].
Desired ordering:   [1 2 3 4]

Another example:

N = 4; P = [2 1;
            2 4];
Possible orderings: [2 1 3 4], [2 1 4 3], [2 3 1 4], [2 3 4 1],
                    [2 4 1 3], [2 4 3 1], [3 2 1 4], [3 2 4 1].
Desired ordering:   [2 1 3 4]

Write a function that takes N and P, then output the desired ordering.

You are ensured that 1 <= N <= 100 and 1 <= K <= 100. All elements of P are within [1, N]. Furthermore, none of the constraints will be conflicting.

Solution Stats

8.62% Correct | 91.38% Incorrect
Last Solution submitted on Jun 12, 2020

Problem Comments