Undirected connected graph - Finding edges with specific weight that belong to MST

Question

the question:

Given an undirected connected graph G, with weight on its edges and specific weight X,
write algorithm that's finding all the edges in G with weight X that belong to some MST of G

apparently you can do it in linear time complexity O(V+E).

• my approach here is to sort the edges(ascending order), then remove all edges of weight X and above, run DFS on the graph, then to check every edge of weight X if when adding the edge, the graph is connected, if so then this edge of weight X does belong to a MSB

but i think im missing here something in the algorithm(what if i have a cycle where all the edges are of weight X for example), and about the time complexity sorting will take (E * Log(E)), DFS will take O(V+E) is (V+E) better or worse then (Elog(E))?

and in addition i need to check for each edge that im "checking" if the graph is still connected (so how could i do that in O(V+E)? wouldnt running dfs again would take more time because i need to run dfs - as the amount of edges of weight X)?

Answer 1

You can solve this in linear time by adapting Kruskal's algorithm:

1. Make the subgraph of G containing only edges with weight less than X;

2. Find the connected components of this subgraph, and label each vertex with a number corresponding to its connected component;

3. Find all the edges with weight X that connect vertices with different labels, or with at least one unlabeled adjacent vertex. Each of those is in at least one MST.