# find all edges in a weighed tree that are heaviest edges in some cycle

Given an undirected graph $G=(V,E)$ and a weight function $w:E\to\{1,2,3,\dots,10\}$:

Let $U\subseteq E$ the set of all edges $e\in E$ that has a cycle in $G$ such that the cycle contains $e$ and all the edges in the cycle are not of heavier weight than $e$.

Find an algorithm that computes $U$.

I have found an algorithm to do it using a modified version of Kruskal algorithm and the union find data structure in $\mathcal{O}(|V|+|E|\alpha(|V|,|E|)$.

My TA said that it can be computed using a linear time algorithm, can you help? I thought of something about modifying the Prim algorithm and then using $10$ Queues for each weight.

• 1. You seem to have already figured out that this problem is an obfuscated form of a slight restriction of a very well-known graph theory problem; why not spell this out, to save answerers some time? 2. Hint: First consider a restriction in which every edge has weight 1. What algorithm solves this problem? – j_random_hacker May 5 '17 at 17:44
• Hint: there are only 10 possible values for the weight. You can do all sorts of things, like sorting by weight, in $O(1)$ time per edge (e.g., counting sort). – D.W. May 5 '17 at 18:50
• @j_random_hacker If all edges are of weight $1$ we just need to run DFS and find all back edges in linear time. But how can we expand this? – Don Fanucci May 5 '17 at 19:38
• @D.W. I used sorting in $\mathcal{O}(1)$ for the modified Kruskal algorithm but still you have to use the union find which makes the algorithm above linear time. – Don Fanucci May 5 '17 at 19:40
• @j_random_hacker Thank you I figured it out! – Don Fanucci May 5 '17 at 19:50