Kruskal Algorithm

Problem

Given the number of vertices n and bidirectional edge information edges, write a function solution that applies the Kruskal algorithm to return the edge numbers included in the minimum spanning tree (MST), in the order they are processed.

If there are multiple edges with the same weight during the Kruskal algorithm process, prioritize edges with smaller edge numbers.

The edge numbers are determined by the order of edges in the edges input.
(The first edge in edges has edge number 1, the second edge has edge number 2, and so on.)

It is assumed that the input graph is connected (a path exists between any two vertices).
The graph always guarantees the existence of an MST.

Concept Explanation

The Minimum Spanning Tree (MST) refers to a spanning tree of a given bidirectional graph with the minimum total edge weight.
Reference: Minimum Spanning Tree

Two common algorithms to find an MST are Prim's algorithm and Kruskal's algorithm.

The Kruskal algorithm proceeds as follows:

1. Sort the E edges in ascending order of their weights.
2. Check if the two endpoints of the edge with the smallest weight are already connected.
3. If the endpoints are connected, skip the edge. Otherwise, include the edge in the MST and connect the two vertices.
4. Repeat steps 2-3 until all vertices are connected.

The Kruskal algorithm has a time complexity of $O(E \log V)$.

For example, consider the following connected graph, where the edges are numbered in input order, and X, Y represent the vertex numbers:

After sorting the edges in ascending order of weights (breaking ties by edge number), the result is:

Next, process edges in order of increasing weight. For edge 8, vertices 6 and 3 are not connected, so include it in the MST:

For edge 6, vertices 3 and 2 are not connected, so include it in the MST:

Similarly, include edges 2 and 1:

For edge 7, vertices 2 and 4 are already connected, so skip this edge:

For edge 3, vertices 4 and 6 are already connected, so skip this edge:

Finally, include edge 5:

Continue this process until all vertices are connected or all edges are processed. The final MST is:

Constraints

• The number of vertices n is a natural number between 2 and 50,000 inclusive.
• Each element in edges represents a bidirectional edge with two endpoints x, y, and edge weight w:
  • edges contains up to 200,000 edges.
  • x, y are natural numbers between 1 and n inclusive.
  • w is a natural number up to 10,000 inclusive.

Test Case

Explanation for Test Case 1

• This corresponds to the example graph described in the explanation above.

Explanation for Test Case 2

• The given graph is already a tree, so all edges are included in the MST, added in order of edge weights.