Min Cost to Connect All Points

min_heap = [[0, 0]]

Initialize min-heap with starting point 0 and cost 0.

Starting the MST from point 0 with zero cost seeds the algorithm and ensures the heap always has candidate edges.

cost, i = heapq.heappop(min_heap)

Pop the smallest cost edge from the heap.

Selecting the minimal edge ensures the MST grows optimally by always adding the least costly connection.

return res

Return the total cost of the MST after all points are connected.

The accumulated cost represents the minimum cost to connect all points with no cycles, fulfilling the problem requirement.

dist = abs(x1 - x2) + abs(y1 - y2)

Calculate Manhattan distance between points i and j.

Manhattan distance defines the edge weight, which is the cost to connect these two points.

visit = set()

Create a set to track visited points.

Visited set prevents cycles and ensures each point is added to the MST exactly once.

if i in visit:

Skip if the point is already visited.

Avoids cycles and redundant processing by ignoring edges leading to points already in the MST.

res += cost

Add the edge cost to the total MST cost.

Accumulates the cost of the newly added edge, progressively building the MST's total cost.

visit.add(i)

Mark the current point as visited.

Records that this point is now part of the MST, preventing future cycles and redundant edges.

if nei not in visit:

Check if neighbor point is unvisited.

Only unvisited neighbors are candidates for MST expansion, ensuring no cycles are formed.

heapq.heappush(min_heap, [nei_cost, nei])

Push neighbor edge into the min-heap for future consideration.

Adds candidate edges to the heap, maintaining the priority queue of minimal edges for MST growth.

adj = { i:[] for i in range(N) }

Initialize adjacency list as a dictionary with empty lists for each point.

This data structure will hold all edges for each point, enabling efficient access to neighbors and their edge costs.

adj[i].append([dist, j])

Add edge from i to j with computed distance.

Storing this edge in adjacency list allows quick access to neighbors during MST construction.

adj[j].append([dist, i])

Add edge from j to i with computed distance to maintain undirected graph.

Ensures the graph is undirected by storing edges in both directions, which is essential for correct MST traversal.

while len(visit) < N:

Loop until all points are visited.

Ensures the MST spans all points by continuing until every point is included.

continue

Continue to next iteration if point was visited.

This control flow prevents adding duplicate edges and maintains correctness of MST construction.

for nei_cost, nei in adj[i]:

Iterate over neighbors of the current point.

Explores all edges from the newly added point to unvisited points, expanding the MST frontier.

for i in range(N):

Iterate over each point index i to build edges.

Outer loop to pair each point with all subsequent points, ensuring all edges are considered once.

for j in range(i + 1, N):

Iterate over each point index j greater than i to avoid duplicate edges.

Inner loop pairs point i with all points after it, ensuring each edge is processed once and stored bidirectionally.

res = 0

Initialize result variable to accumulate total MST cost.

This variable will sum the costs of all edges included in the MST.

N = len(points)

Store the number of points in variable N.

Caching the number of points avoids repeated calls to len(points) and clarifies the problem size for subsequent loops.

x1, y1 = points[i]

Extract x and y coordinates of point i.

Coordinates are needed to compute Manhattan distances to other points.

x2, y2 = points[j]

Extract x and y coordinates of point j.

Coordinates of the second point in the pair are required for distance calculation.