CareerCup

public class MinimumCostToConstructRoad {
        public class GraphMinHeap<T> where T : IComparable {
            T[] hp = null;
            Hashtable keytoIndex = null;
            int Size = 0;
            public GraphMinHeap (int size) {
                hp = new T[size];
                keytoIndex = new Hashtable ();
            }
            public int GetParentIndex (int i) {
                return i - 1 / 2;
            }
            public int GetLeftChildIndex (int i) {
                return 2 * i + 1;
            }
            public int GetRightChildIndex (int i) {
                return 2 * i + 2;
            }
            public void Enqueue (T data) {
                this.keytoIndex.Add (data, Size);
                this.hp[Size] = data;
                if (this.Size > 0) {
                    this.HeapifyUP (this.Size);
                }
                this.Size++;
            }
            public T Peek () {
                if (this.Size == 0) {
                    throw new Exception ("Heap is empty");
                }
                return this.hp[0];
            }
            public T Dequeue () {
                if (this.Size == 0) {
                    throw new Exception ("Heap is empty");
                }
                var result = this.hp[0];
                this.Size--;
                if (this.Size != 0) {
                    this.Swap (0, this.Size);
                    this.HeapifyDown (0);
                }
                return result;
            }
            public bool IsContain (T key) {
                return this.keytoIndex.Contains (key);
            }
            public void DecreaseKey (T key, T newValue) {
                if (this.keytoIndex.Contains (key) == false) {
                    throw new Exception ("Key not found in heap");
                }
                int keyIndex = (int) this.keytoIndex[key];
                this.keytoIndex.Remove (key);
                this.hp[keyIndex] = newValue;
                this.keytoIndex.Add (newValue, keyIndex);
                this.HeapifyUP (keyIndex);
            }
            public bool IsEmpty () {
                return this.Size > 0;
            }
            public void Swap (int i, int j) {
                T temp = this.hp[i];
                this.hp[i] = this.hp[j];
                this.hp[j] = temp;
                this.keytoIndex[this.hp[i]] = i;
                this.keytoIndex[this.hp[j]] = j;
            }
            public void HeapifyUP (int i) {
                while (true) {
                    if (i <= 0) {
                        break;
                    }
                    int parentIndex = this.GetParentIndex (i);

                    if (this.hp[i].CompareTo (this.hp[parentIndex]) >= 0) {
                        break;
                    }
                    this.Swap (parentIndex, i);
                    i = parentIndex;
                }
            }
            public void HeapifyDown (int i) {
                while (true) {
                    int leftChildIndex = this.GetLeftChildIndex (i);
                    int rightChildIndex = this.GetRightChildIndex (i);
                    if (leftChildIndex > this.Size) {
                        break;
                    }
                    int minChildIndex = leftChildIndex;
                    if (rightChildIndex < this.Size &&
                        this.hp[rightChildIndex].CompareTo (this.hp[leftChildIndex]) <= 0) {
                        minChildIndex = rightChildIndex;
                    }
                    if (this.hp[i].CompareTo (this.hp[minChildIndex]) <= 0) {
                        break;
                    }
                    this.Swap (i, minChildIndex);
                    i = minChildIndex;

                }
            }

        }
        public class SimpleVertex : IComparable {
            public int Weight {
                get;
                set;
            }
            public int Data {
                get;
                set;
            }
            public List<SimpleEdge> Edges {
                get;
                set;
            }
            public SimpleVertex (int data) {
                this.Data = data;
                this.Weight = int.MaxValue;
                this.Edges = new List<SimpleEdge> ();
            }

            public int CompareTo (object obj) {
                var other = (SimpleVertex) obj;
                if (this.Weight == other.Weight) {
                    return 0;
                } else if (this.Weight > other.Weight) {
                    return 1;
                } else {
                    return -1;
                }
            }
        }
        public class SimpleEdge {
            public SimpleVertex Source {
                get;
                set;
            }
            public SimpleVertex Destination {
                get;
                set;
            }
            public int Weight {
                get;
                set;
            }
            public SimpleEdge (SimpleVertex source, SimpleVertex destinaion, int weight) {
                this.Source = source;
                this.Destination = destinaion;
                this.Weight = weight;
            }
        }
        public class SimpleGraph {

            private Dictionary<int, SimpleVertex> vertices = new Dictionary<int, SimpleVertex> ();
            public int NumberOfVertices {
                get;
                set;
            }
            public List<SimpleVertex> GettAllVertices () {
                return this.vertices.Values.ToList ();
            }
            public SimpleGraph (int numberOfVertices) {
                this.NumberOfVertices = numberOfVertices;
            }
            public void AddEdge (int x, int y, int weight) {
                SimpleVertex source = null;
                if (this.vertices.ContainsKey (x)) {
                    source = (SimpleVertex) this.vertices[x];
                } else {
                    source = new SimpleVertex (x);
                    this.vertices.Add (x, source);
                }
                SimpleVertex destinaion = null;
                if (this.vertices.ContainsKey (y)) {
                    destinaion = (SimpleVertex) this.vertices[y];
                } else {
                    destinaion = new SimpleVertex (y);
                    this.vertices.Add (y, destinaion);
                }
                var edge = new SimpleEdge (source, destinaion, weight);
                source.Edges.Add (edge);
            }
            public IList<SimpleEdge> GetMST (SimpleGraph graph) {
                // map of vertex to edge which will give minimum weight to this vertex
                var vertexToEdge = new Dictionary<SimpleVertex, SimpleEdge> ();
                // store final result
                List<SimpleEdge> result = new List<SimpleEdge> ();
                // binary heap + map data structure
                var pq = new GraphMinHeap<SimpleVertex> (graph.NumberOfVertices + 1);
                // insert all vertices to pq
                foreach (var vertex in graph.GettAllVertices ()) {
                    pq.Enqueue (vertex);
                }
                var startVertex = graph.GettAllVertices () [0];
                // decrease the weight of startvertex to 0
                startVertex.Weight = 0;
                pq.DecreaseKey (startVertex, startVertex);
                // iterate till heap + map datastructure has element in it.
                while (pq.IsEmpty ()) {
                    // get miniumu weight value from pq
                    var current = pq.Dequeue ();

                    //get the corresponding edge for this vertex if present and add it to final result.
                    //This edge wont be present for first vertex.
                    if (vertexToEdge.ContainsKey (current)) {
                        result.Add (vertexToEdge[current]);
                    }
                    // iterate through all the adjacent vertices
                    foreach (var edge in current.Edges) {
                        //check if adjacent vertex exist in heap + map and weight attached with this 
                        // vertex is greater than this edge weight
                        var neighbour = this.GetVertexForEdge (current, edge);
                        if (pq.IsContain (neighbour) && neighbour.Weight > edge.Weight) {
                            //decrease the value of adjacent vertex to this edge weight.
                            neighbour.Weight = edge.Weight;
                            pq.DecreaseKey (neighbour, neighbour);
                            //add vertex->edge mapping in the graph.
                            vertexToEdge[neighbour] = edge;
                        }
                    }
                }
                return result;
            }
            private SimpleVertex GetVertexForEdge (SimpleVertex vertex, SimpleEdge edge) {
                if (edge.Source.Equals (vertex)) {
                    return edge.Destination;
                } else {
                    return edge.Source;
                }
            }
        }
        /*
        
        Time complexity : Heap + Map data structure  has foure functions
        1) Enqueue : O(logV)
        2) Dequeue : O(logV)
        3) Contain : O(1)
        4) DecreaseKey : O(logV)
        In wrost case it migth need to stroe entire vertices to heap + map data structure
        O(Elog(V))
        Space Complexity: Storing MST edges in list , map to keep track vertex to edge and heap + map data structure
        So in wrost case it will be O(V + E). Because we might end up stroing all edges of graph.

         */
        public int getMinimumCostToConstruct (int numTotalAvailableCities,
            int numTotalAvailableRoads,
            int[, ] roadsAvailable,
            int numNewRoadsConstruct,
            int[, ] costNewRoadsConstruct)

        {
            var graph = new SimpleGraph (numTotalAvailableCities);
            for (int i = 0; i < roadsAvailable.GetLength (0); i++) {
                graph.AddEdge (roadsAvailable[i, 0], roadsAvailable[i, 1], 0);
            }
            for (int i = 0; i < costNewRoadsConstruct.GetLength (0); i++) {
                graph.AddEdge (costNewRoadsConstruct[i, 0], costNewRoadsConstruct[i, 1], costNewRoadsConstruct[i, 2]);
            }
            var mstedges = graph.GetMST (graph);
            int result = 0;
            foreach (var edge in mstedges) {
                result += edge.Weight;
            }
            return result;
        }
    }

Use Kruskal's to find out the MST. Use a DSU to maintain already connected nodes. Initialize DSU with already built nodes.

public static void solve(ArrayList<Pair<Integer, Integer>> available, ArrayList<Pair<Pair<Integer, Integer>, Integer>> cost) {
        HashMap<Integer, Integer> costMap = new HashMap<Integer, Integer>();
        for (int i = 1; i < available.size(); i++) {
            costMap.put(available.get(i).getValue(), 0);
        }

        for( Pair<Pair<Integer, Integer>, Integer> pair : cost ) {
            Integer key = pair.getKey().getValue() ;
            Integer existing = costMap.get(key) ;
            if( existing == null || existing > pair.getValue() ) {
                costMap.put(key, pair.getValue()) ;
            }
        }

        int total = 0 ;
        for( Integer key : costMap.keySet() ) {
            total += costMap.get(key) ;
        }

        System.out.println(total);

}

public static void solve(ArrayList<Pair<Integer, Integer>> available, ArrayList<Pair<Pair<Integer, Integer>, Integer>> cost) {
        HashMap<Integer, Integer> costMap = new HashMap<Integer, Integer>();
        for (int i = 1; i < available.size(); i++) {
            costMap.put(available.get(i).getValue(), 0);
        }

        for( Pair<Pair<Integer, Integer>, Integer> pair : cost ) {
            Integer key = pair.getKey().getValue() ;
            Integer existing = costMap.get(key) ;
            if( existing == null || existing > pair.getValue() ) {
                costMap.put(key, pair.getValue()) ;
            }
        }

        int total = 0 ;
        for( Integer key : costMap.keySet() ) {
            total += costMap.get(key) ;
        }

      System.out.println(total);
    }