1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Klio2033 [76]
3 years ago
12

Your job is to prepare a lineup of n awardees at an award ceremony. You are given a list of m constraints of the form "i wants t

o receive an award before j." If you violate a constraint, it might upset the affected award recipient (i) and then i may leave the ceremony. Give an algorithm that prepares such a lineup, (or says that it is not possible) in O ( m + n ) time.
Mathematics
1 answer:
DanielleElmas [232]3 years ago
6 0

Answer:

The idea is to use the concept of topological sorting.

Complexity of this algorithm is equal to complexity of DFS algorithm, that is, O(m+n).

Step-by-step explanation:

The idea is to use the concept of topological sorting.

A topological sort also called a topological ordering of a directed graph is a linear ordering of its vertices in a way that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

A topological sorting is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

For every edge (U - - >V), create a directed edge from U to V.

While creating an edge, if an edge creates a cycle, then it is not possible.

n= number of awardees

m= the number of constraint

Let n represent the vertices of a graph and constraints m is representing edges of a graph.

and graph is represented in adjacent of O(m+n)

Constraint i wants to receive award before j

Graphical representation - - - - - > (i) - - - - - - > (j) j depends on i

1. Presently run topological olding on graph G(n, m) where n is vertices and m is edges.

2. Run DFs on Graph, a temporary stack

3. Firstly call topological sorting for all its adjacent vertices and then push it to a stack. Finally, print content of stack.

4. Vertex is push to stack only when all adjacent vertices are already in stack.

Complexity of this algorithm is equal to complexity of DFS algorithm, that is, O(m+n).

You might be interested in
What is the value of x in the equation x – y = 30, when y = 15?
iogann1982 [59]
The answer is 45, because if you have 45(x)-15(y)=30
5 0
3 years ago
Read 2 more answers
Which values are solutions to × > 7? A. × = 11 and × = 1 B. × = 0 and × = 8 C. × = 8 and × = 11 D. × = -8 and × = 0
ivanzaharov [21]

Answer:

C

Step-by-step explanation:

6 0
3 years ago
Figure WXYZ is a rectangle. What are the<br> coordinates of point W?
Andre45 [30]

Answer:

(2,9)

Step-by-step explanation:

3 0
3 years ago
Read 2 more answers
Unit cubes and solid figures
s344n2d4d5 [400]
The dimensions are 10 x 10 x 10. I this is because when it was it can hold up to 1000 cubes, that says the volume is 1000. I know that V=lwh so 1000 = lwh. If you do 10 x 10 x 10 you get 100! Hope this helped :D

Please mark me the brainiest!
5 0
3 years ago
A____ is a fixed position in space and has no dimensions or size. hins​
amid [387]

Answer:

Point

Step-by-step explanation:

This is the definition of a point.

A "point" is a fixed position in space and has no dimensions or size.

Cheers.

6 0
3 years ago
Read 2 more answers
Other questions:
  • One leg of a right triangle has a length of 5 m. The other lengths that are consecutive integers
    14·2 answers
  • A soda can has a diameter of 6 cm. What is the circumference of the can?
    12·1 answer
  • There are 9 cherry cokes, 3 diet cokes, and 4 coke zeros in a cooler. What is the proabiliyt of selecting a drink and getting a
    14·1 answer
  • Calculate the length of CD if the area of △BCD is 150 cm ²
    6·1 answer
  • Which number produces a rational number when added to 0.5?
    14·1 answer
  • Solve the problem 1/5+2/5+3/5=
    15·2 answers
  • Please help me with these question.
    8·2 answers
  • 178·37−37·78 <br> Plz find in binary<br> If not able: Say no solution.
    5·1 answer
  • Can i have help with these two questions. Im not sure where i went wrong
    12·1 answer
  • What is m∠G?<br><br><br><br><br><br> Enter your answer in the box.
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!