Amazon | OA 2019 | Min Cost to Connect All Nodes

Posted on | Edited on | Views:

link

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
import java.util.*;

class kruskalMST {

    static class Edge {
        int source;
        int destination;
        int weight;

        Edge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
        // void printEdge(){
        //     System.out.println("source:"+this.source+",destination:"+this.destination+",weight:"+this.weight);
        // }
    }

    static class Graph {
        int vertex;
        ArrayList<Edge> allEdges;

        Graph(int vertex) {
            this.vertex = vertex;
            allEdges = new ArrayList<>();
        }

        void addEdge(int source,int destination,int weight){
            Edge edge=new Edge(source, destination, weight);
            allEdges.add(edge);
        }

        void makeSet(int[] parent){
            for(int i=0;i<parent.length;i++){
                parent[i]=i;
            }
        }

        int find(int[] parent, int v){
            while(parent[v]!=v) return find(parent, parent[v]);
            return v;
        }

        void union(int[] parent, int a, int b){
            int aRoot=find(parent, a);
            int bRoot=find(parent, b);
            parent[bRoot]=aRoot;
        }

        int MST_minCost(){
            PriorityQueue<Edge> q=new PriorityQueue<>(this.vertex,(a,b)->a.weight-b.weight);
            for(Edge singleEdgle:allEdges) q.offer(singleEdgle);

            int[] parent=new int[this.vertex];
            makeSet(parent);

            int res=0;
            int idx=0;
            while(idx<vertex-1){
                Edge edge=q.poll();
                // edge.printEdge(); // print edge
                int x=find(parent, edge.source);
                int y=find(parent, edge.destination);
                if(x!=y){
                    res+=edge.weight;
                    idx++;
                    union(parent, x, y);
                }
            }
            return res;
        }
    }
}
/*
public class MyClass {
    public static void main(String[] args) {
        int n = 6;
        int[][] edges = { { 1, 4 }, { 4, 5 }, { 2, 3 } };
        int[][] newEdges = { { 1, 2, 5 }, { 1, 3, 10 }, { 1, 6, 2 }, { 5, 6, 5 } };
        kruskalMST.Graph graph=new kruskalMST.Graph(n);
        for(int[] edge:edges) graph.addEdge(edge[0]-1, edge[1]-1, 0);
        for(int[] edge:newEdges) graph.addEdge(edge[0]-1, edge[1]-1, edge[2]);
        System.err.println(graph.MST_minCost());
    }
}*/

0%