https://www.acmicpc.net/problem/4386
initial
So we are trying to find the min distance to link all the stars together. I didnt have a clue how so I headed on to question forum but spoiler alert, I saw Kruskal algorithm. I thought alas it is MST! How did I miss that!
So unlike the typical kruskal/MST problem, the cost of travelling from a node to another node is not given. Thus we have to compute it ourselves. Also the node is given in x,y position so we have to use a for loop.
My initial idea was to first draft a 2x2 graph what is symmetrical about i==j axis and marking the cost to travel from nodes and vice versa through the euclidean distance formula like this
graph = [[0 for _ in range(n)] for _ in range(n)]
ans = 0
def calc_distance(x1, y1, x2, y2):
return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
for i in range(n):
for j in range(n):
if i == j:
continue
if graph[i][j] != 0:
continue
from_point = lst[i]
to_point = lst[j]
graph[i][j] = calc_distance(from_point[0], from_point[1], to_point[0], to_point[1])
graph[j][i] = calc_distance(from_point[0], from_point[1], to_point[0], to_point[1])But for MST, we need info of all the costs from node to node typically in 1d list cuz we need to sort and iterate the edge with the lowest cost first. So then I realised my 2x2 graph wasnt necessary to compute at all because I could have just initialised a edges 1d list and iterate i from 0 to n and j from i+1 to n. These i and j signify the node numbers and i can get the from x from y by getting the value with lst[i] and to x to y with lst[j]. Then we can compute the euclideian distance and just append to this edges list. My initial idea of using a for loop and appending graph[i][j] with i and j to edges list was logically correct but yea it could have been better.
mistake in union
Then, we do the typical find_parent and union BUT i keep making this deadly mistake in union. Omg for union i keep making the same mistaking of making parent of node2 as parent 1. It should be parent of parent2 should be parent1, not node2. Lets logically think this through. Union means we are trying to combine 2 sets together. We combine via assigning parents together, not the nodes!
deadly mistake revisited aug 19th 2025
and i didnt directly use the find_parent function in union. Instead i wrongly did parent[node]. This wont get and update u with the deepest parent.
wrong:
def union(node1, node2):
par1 = find_parent(node1)
par2 = find_parent(node2)
if par1 < par2:
parent[node2] = par1
else:
parent[node1] = par2correct:
def union(node1, node2):
par1 = find_parent(node1)
par2 = find_parent(node2)
if par1 < par2:
parent[par2] = par1
else:
parent[par1] = par2solution
as mentioned we dont need the graph and calculation of cost cuz we can do it right when appending to edges list.
import math,sys
input =sys.stdin.readline
n = int(input())
lst = []
for _ in range(n):
a, b = map(float, input().split())
lst.append((a, b))
graph = [[0 for _ in range(n)] for _ in range(n)]
ans = 0
def calc_distance(x1, y1, x2, y2):
return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
for i in range(n):
for j in range(n):
if i == j:
continue
if graph[i][j] != 0:
continue
from_point = lst[i]
to_point = lst[j]
graph[i][j] = calc_distance(from_point[0], from_point[1], to_point[0], to_point[1])
graph[j][i] = calc_distance(from_point[0], from_point[1], to_point[0], to_point[1])
edges = []
for i in range(n):
for j in range(i + 1, n):
cost=math.sqrt((lst[i][0]-lst[j][0])**2 +(lst[i][1]-lst[j][1])**2)
edges.append((i,j,cost))
edges.sort(key=lambda x: x[2])
parent = [i for i in range(n)]
def find_parent(node):
if parent[node] != node:
parent[node] = find_parent(parent[node])
return parent[node]
def union(node1, node2):
par1 = find_parent(node1)
par2 = find_parent(node2)
if par1 < par2:
parent[par2] = par1
else:
parent[par1] = par2
for edge in edges:
node1, node2,cost = edge
if find_parent(node1) != find_parent(node2):
union(node1, node2)
ans += cost
print(f"{ans:.2f}")java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Main {
static int[] parent;
public static int find_parent(int[] parent, int node){
if(parent[node]!=node){
parent[node] = find_parent(parent,parent[node]);
}
return parent[node];
}
public static void union(int node1,int node2){
int parent1 = find_parent(parent,node1);
int parent2 = find_parent(parent,node2);
if(parent1<parent2){
parent[parent2]=parent1;
} else {
parent[parent1]=parent2;
}
}
public static double calc_distance(double x1, double y1, double x2, double y2){
return Math.sqrt(Math.pow(x2-x1,2) + Math.pow(y2-y1,2));
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());
List<double[]> points = new ArrayList<>();
for(int i=0;i<n;i++){
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
double a = Double.parseDouble(stringTokenizer.nextToken());
double b = Double.parseDouble(stringTokenizer.nextToken());
points.add(new double[]{a,b});
}
List<List<Object>> list = new ArrayList<>();
for(int i =0;i<n;i++){
for(int j =i+1;j<n;j++){
double cost = calc_distance(points.get(i)[0], points.get(i)[1], points.get(j)[0], points.get(j)[1]);
list.add(Arrays.asList(i,j,cost));
}
}
list.sort(Comparator.comparingDouble(a -> (Double) a.get(2)));
parent = new int[n];
for(int i =0;i<n;i++){
parent[i]=i;
}
double ans =0;
for (List<Object> point:list){
int node1 = (int) point.get(0);
int node2 = (int) point.get(1);
double val = (double) point.get(2);
if (find_parent(parent,node1)!=find_parent(parent,node2)){
union(node1,node2);
ans+=val;
}
}
System.out.printf("%.2f%n",ans);
}
}
complexity
The time complexity of your algorithm depends on the sorting step, which dominates the overall complexity. If we denote the number of edges as E (which is roughly n^2/2 in your case), the time complexity is O(E log E) due to the sorting step. Therefore, the overall time complexity is O(n^2 log n) since E is proportional to n^2.
The space complexity is dominated by the graph representation and the edges list. The space complexity is O(n^2) for the graph, and O(E) for the edges list. Therefore, the overall space complexity is O(n^2).
