Implementation - Edges in MST

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: $O(E \log E)$. Space: $O(V)$.