1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| class Solution {
public int minCostConnectPoints(int[][] points) {
//number of nodes/vertices
int n = points.length;
//number of edges = nC2 -> n*(n-1)/2
int e = n*(n-1)/2;
//to store all edges with their weights
int[][] edges = new int[e][3];
//to add edge info at index idx in edges array
int idx=0;
//loop through all the points combinations
//each combination can form an edge with weight = |x1-x2| + |y1-y2|
for(int i=0; i<n; i++){
//we start with j=i+1 to avoid duplicate (point A to point B is same as point B to point A)
for(int j=i+1; j<n; j++){
//calculate the weight of that edge
int w = Math.abs(points[i][0]-points[j][0]) + Math.abs(points[i][1]-points[j][1]);
//store edge info
edges[idx][0] = i;
edges[idx][1] = j;
edges[idx][2] = w;
//increment edge count
idx++;
}
}
//the minimum cost is the MST
return spanningTree(n, e, edges);
}
//Minimum Spanning Tree
static int spanningTree(int V, int E, int edges[][]){
Arrays.sort(edges, (o1, o2) -> o1[2] > o2[2]?1: (o1[2] < o2[2]?-1:0));
//init parent array -> initially with no edges, every node will be its own parent
int[] parent = new int[V];
for(int i=0; i<parent.length; i++){
parent[i] = i;
}
//init total cost
int cost = 0;
//check for each edge if it can be included
for(int i=0; i<E; i++){
//get the nodes forming the current edge
int u = edges[i][0];
int v = edges[i][1];
//if both the nodes are part of the same connected component, we cannot choose it as they will form a cycle if included
//if they have different leaders, they can be merged as a single component. pick that edge and add the cost
if(union(u, v, parent)){
cost += edges[i][2];
}
}
return cost;
}
public static int find(int x, int[] parent){
while(parent[x] != x){
x = parent[x];
}
return parent[x];
}
public static boolean union(int x, int y, int[] parent){
//if parent of x and y are same, union is not needed so return false
if(find(x, parent) == find(y, parent)) return false;
//else, merge them and return true
//to merge them, we need to change the parent of the leader of one component as the leader of second component
parent[find(x, parent)] = find(y, parent);
return true;
}
}
|
