This post is a continuation to this.
In this post we will be discussing the solution to the second problem. You can find it here.
There are N files in a package. To compile them you need to compile each file individually. However some of these files require other files to be compiled first. Given N files and M relations denoting dependencies of one file on other, you need to find order of compiling the files. If there are more than one orders , find the one which is lexicographically largest.
The key to solving this problem is to model the given input as a proper data structure.
The given files can be considered as nodes of a graph with the dependency relations as edges. The dependency relations are not symmetric i.e if x requires y to compile then y would not require x to compile. Thus the graph is unweighted, acyclic and directed.
The order in which the files must be compiled is now simply a topological ordering of the graph. A topological ordering T of a directed acyclic graph (DAG), is ordering of vertices such that for every edge from any vertex v to any other vertex u , v appears somewhere before u.
However a DAG can have any number of topological orderings. The question asks for the one which is lexicographically largest.
There are many ways to do this, however the below mentioned one is very easy to implement for our case.
As the given graph is acyclic there exists at least one vertex with in-degree 0. The following algorithm constructs a topological ordering:
While there are vertices in graph:
Pick a vertex with in-degree 0, add it to the required order and remove the vertex from the graph along with all its out going edges.
In case there are more than one vertices with 0 in-degree pick the one which is represented by a bigger number.
To implement this one can use a priority queue with vertices ordered in the increasing order of in-degree and if the vertices have equal in-degree then the one denoted by a bigger number has a higher priority. At every step remove the top element from the priority queue and decrease the in-degree of all vertices to which the removed vertex has an edge by one.
Time Complexity:
For the graph with N vertices and M edges
We pick the top priority element from the queue N times and decrease the in-degree a total M times.
Getting the top element from a priority queue is O(logN) and decreasing an element is also O(logN), if the queue is implemented as a heap.
So the time complexity is O((N+M).logN).
In this post we will be discussing the solution to the second problem. You can find it here.
There are N files in a package. To compile them you need to compile each file individually. However some of these files require other files to be compiled first. Given N files and M relations denoting dependencies of one file on other, you need to find order of compiling the files. If there are more than one orders , find the one which is lexicographically largest.
The key to solving this problem is to model the given input as a proper data structure.
The given files can be considered as nodes of a graph with the dependency relations as edges. The dependency relations are not symmetric i.e if x requires y to compile then y would not require x to compile. Thus the graph is unweighted, acyclic and directed.
The order in which the files must be compiled is now simply a topological ordering of the graph. A topological ordering T of a directed acyclic graph (DAG), is ordering of vertices such that for every edge from any vertex v to any other vertex u , v appears somewhere before u.
However a DAG can have any number of topological orderings. The question asks for the one which is lexicographically largest.
There are many ways to do this, however the below mentioned one is very easy to implement for our case.
As the given graph is acyclic there exists at least one vertex with in-degree 0. The following algorithm constructs a topological ordering:
While there are vertices in graph:
Pick a vertex with in-degree 0, add it to the required order and remove the vertex from the graph along with all its out going edges.
In case there are more than one vertices with 0 in-degree pick the one which is represented by a bigger number.
To implement this one can use a priority queue with vertices ordered in the increasing order of in-degree and if the vertices have equal in-degree then the one denoted by a bigger number has a higher priority. At every step remove the top element from the priority queue and decrease the in-degree of all vertices to which the removed vertex has an edge by one.
Time Complexity:
For the graph with N vertices and M edges
We pick the top priority element from the queue N times and decrease the in-degree a total M times.
Getting the top element from a priority queue is O(logN) and decreasing an element is also O(logN), if the queue is implemented as a heap.
So the time complexity is O((N+M).logN).
No comments:
Post a Comment