# Hints: Minimal Labels

We were smart enough to figure out that instead of assigning all 5 labels at once, we should assign label 1 and unlock some vertices. However, notice that label 1 is most precious. What if you had unlocked new vertices by utilising the less valuable labels, for example, label 5? In that case, you might have gotten better candidates for Label 1.

Assign the least valuabel valuable (Label 5) and unlock new vertices. Is this strategy correct?

Even this strategy is wrong. What if the most important candidate for label 5 is hiding behind vertex 4?

Consider this counter example.

```
4 --> 1
2 --> 3
```

The least valuable label is Label `n`

. Hence, if we can assign this to the least valuable candidate that can afford this label, then we will always preserve the important labels for important candidates.

Using this, come up with an algorithm to solve the problem.

Candidates for label `n`

are vertices with outdegree 0. Amongst these candidates, you should assign the label to the one with highest index. Then, delete this vertex from the graph, unlocking a new set of vertices with outdegree zero.

Why is the algorithm correct? How do you delete sink vertices from a graph? How do you efficiently retrieve the highest index vertex with outdegree 0?

**Transpose Graph**. To efficiently retrieve highest index vertex, use a

**set**with keys

`(outdegree, index)`

with a custom comparator that sorts it by smaller outdegree first and then bigger index next.