Here is the edge classification approach:
function edgesInMST(n, edges):
sort edges by weight
parent = array [0, 1, 2, ..., n]
mstEdges = set
// Build MST with Kruskal
for (i, (u, v, w)) in enumerate(edges):
if find(u) != find(v):
union(u, v)
mstEdges.add(i)
result = array of size edges.length
// Group edges by weight
for each weight group:
// Non-MST edges: check if path exists in MST
for edge (u, v, w) not in MST:
if find(u) == find(v):
result[edge] = "at least one"
else:
result[edge] = "none"
// MST edges: check if removing creates disconnect
for edge (u, v, w) in MST:
if isBridge(u, v, w):
result[edge] = "any"
else:
result[edge] = "at least one"
return result
Time: . Space: .