1+ class Edge {
2+ public int source ;
3+ public int destination ;
4+ public int weight ;// manhattan distance
5+
6+ public Edge (int s ,int d ,int w ){
7+ this .source =s ;
8+ this .destination =d ;
9+ this .weight =w ;
10+ }
11+
12+ @ Override
13+ public String toString () {
14+ return "Edge(u=" +source +", v=" +destination +", w=" +weight +")" ;
15+ }
16+ }
17+
18+ class DisjointSet {
19+ private int []roots ;
20+ private int []ranks ;
21+
22+ public DisjointSet (int n ) {
23+ this .roots =new int [n ];
24+ this .ranks =new int [n ];
25+
26+ // intializing
27+ for (int i =0 ;i <n ;i ++){
28+ this .roots [i ] =i ;
29+ this .ranks [i ] =0 ;// initially ranking 0
30+ }
31+ }
32+
33+ // get the root, use path compression
34+ public int find (int u ) {
35+ if (this .roots [u ] ==u )
36+ return u ;
37+
38+ int root =find (this .roots [u ]);
39+ this .roots [u ] =root ;
40+ return root ;
41+ }
42+
43+ // use ranking
44+ public void union (int x ,int y ) {
45+ int rootX =find (x ),rootY =find (y );
46+ int rankX =this .ranks [rootX ],rankY =this .ranks [rootY ];
47+
48+ if (rootX ==rootY )// already same roots
49+ return ;
50+
51+ if (rankX <rankY ){
52+ // put into rootY
53+ this .roots [rootX ] =this .roots [rootY ];
54+ this .ranks [rootY ]++;
55+ }
56+ else {
57+ // default, put into rootX
58+ this .roots [rootY ] =this .roots [rootX ];
59+ this .ranks [rootX ]++;
60+ }
61+ }
62+
63+ public boolean areDisjoint (int u ,int v ) {
64+ return (find (u ) !=find (v ));
65+ }
66+ }
67+
68+ class Solution {
69+ private int getManhattanDistance (int []p1 ,int []p2 ){
70+ return (
71+ Math .abs (p1 [0 ] -p2 [0 ]) +
72+ Math .abs (p1 [1 ] -p2 [1 ])
73+ );
74+ }
75+
76+ private List <Edge >getEdges (int [][]points ) {
77+ int n =points .length ;
78+ List <Edge >edges =new ArrayList <>();
79+
80+ // edge case
81+ if (n <=1 )
82+ return edges ;
83+
84+ for (int i =0 ;i <(n -1 );i ++){
85+ for (int j =i +1 ;j <n ;j ++){
86+ int w =getManhattanDistance (points [i ],points [j ]);
87+ edges .add (new Edge (i ,j ,w ));
88+ }
89+ }
90+
91+ return edges ;
92+ }
93+
94+ private boolean isEdgeCase (int [][]points ) {
95+ return (points .length <=1 );
96+ }
97+
98+ private int getCostMST (List <Edge >edges ,int numVertices ) {
99+ DisjointSet ds =new DisjointSet (numVertices );
100+ int minCost =0 ,numEdgesTaken =0 ;
101+
102+ for (Edge edge :edges ){
103+ if (ds .areDisjoint (edge .source ,edge .destination )){
104+ ds .union (edge .source ,edge .destination );
105+ numEdgesTaken ++;
106+ minCost +=edge .weight ;
107+ }
108+
109+ if (numEdgesTaken == (numVertices -1 ))// tree is formed, early exit
110+ break ;
111+ }
112+ return minCost ;
113+ }
114+
115+ public int minCostConnectPoints (int [][]points ) {
116+ // edge cases
117+ if (isEdgeCase (points ))
118+ return 0 ;
119+
120+ // edges
121+ List <Edge >edges =getEdges (points );
122+
123+ // sort the edges in ascending order
124+ edges .sort ((x1 ,x2 ) -> (x1 .weight -x2 .weight ));
125+
126+ // Kruskals algorithm for MST [Union Find]
127+ return getCostMST (edges ,points .length );
128+ }
129+ }