HackerRank Prim's (MST) : Special Subtree

In this post, we will solve HackerRank Prim’s (MST) : Special Subtree Problem Solution.

Given a graph which consists of several edges connecting its nodes, find a subgraph of the given graph with the following properties:

The subgraph contains all the nodes present in the original graph.
The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
It is also required that there is exactly one, exclusive path between any two nodes of the subgraph.
One specific node S is fixed as the starting point of finding the subgraph using Prim’s
Algorithm.

Find the total weight or the sum of all edges in the subgraph.
Example
n = 3
edges = [[1, 2, 2], [2, 3, 2], [1, 3, 3]]
start = 1

Starting from node 1, select the lower weight edge, i.e. 1 → 2, weight 2.
Choose between the remaining edges, 13, weight 3, and 2 → 3, weight 2.
The lower weight edge is 2 + 3 weight 2.
All nodes are connected at a cost of 2 + 2 = 4. The edge 1 → 3 is not included in the subgraph.

Function Description

Complete the prims function in the editor below.

prims has the following parameter(s):

int n: the number of nodes in the graph
int edges[m][3]: each element contains three integers, two nodes numbers that are connected and the weight of that edge
int start: the number of the starting node

Returns

int: the minimum weight to connect all nodes in the graph

Input Format
The first line has two space-separated integers n and m, the number of nodes and edges in
the graph.
Each of the next m lines contains three space-separated integers u. v and w, the end nodes of edges[i], and the edge’s weight.
The last line has an integer start, the starting node.

Sample Input 0

Sample Output 0

Explanation 0

The graph given in the test case is shown as :

The starting node is 1 (in the given test case)

Applying the Prim’s algorithm, edge choices available at first are:
1 → 2 (WT. 3) and 1→ 3 (WT. 4), out of which 1→ 2 is chosen (smaller weight of edge). Now the available choices are:
1→ 3 (WT. 4), 2 →3 (WT. 5), 25 (WT. 2) and 2 → 4 (WT. 6), out of which 2 → 5 is chosen by the algorithm.
Following the same method of the algorithm, the next chosen edges, sequentially are:
1 → 3 and 2 → 4.
Hence the overall sequence of edges picked up by Prim’s are:
12:25:13:2 → 4
and the total weight of the MST (minimum spanning tree) is: 3+2+4+6=15

HackerRank Prim's (MST) : Special Subtree Problem Solution — HackerRank Prim’s (MST) : Special Subtree Problem Solution

Prim’s (MST) : Special Subtree C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct nodes {
    int mark;
    int pre;
    int val;
};

int n;
int m;
int s;
int e[3001][3001];
struct nodes node[3001];


int min_mark() {
    int j,m=0,max=100001;
    for(j=1;j<=n;j++) if(node[j].mark!=1 && node[j].val < max) {m=j; max=node[j].val;} 
    return m;
}

void SP(int s) {
    int j;
    for(j=1;j<=n;j++) 
    if(e[s][j]!=-1 && node[j].mark!=1) { 
       if(node[j].pre==0)  {node[j].pre=s; node[j].val= e[s][j];}
       else if(node[j].pre!=0 && node[j].val > e[s][j]) {node[j].pre=s; node[j].val= e[s][j];}   
    }
}

int main() {
    int i,j,k,l,d;
        
    scanf("%d",&n); scanf("%d",&m);
        
    for(k=1;k<=n;k++)
            for(l=1;l<=n;l++) e[k][l]=-1;
            
        for(j=0;j<m;j++) {
            scanf("%d",&k); scanf("%d",&l); scanf("%d",&d);
            if(e[k][l]==-1) e[k][l]=d;
            else if(e[k][l] > d) e[k][l]=d; 
            e[l][k]=e[k][l];
        }
        
    scanf("%d",&s);
    
    //s=1;
        for(k=1;k<=n;k++) {
            if(k==s) {node[k].mark=1; node[k].pre=0; node[k].val=0;}
            else {node[k].mark=0; node[k].pre=0; node[k].val= 100000;}
        }
    SP(s);
        d=min_mark();
        while(d!=0) {node[d].mark=1; SP(d); d=min_mark();}
    d=0;
   for(k=1;k<=n;k++) if(node[k].pre!=0) d+=e[k][node[k].pre];
       printf("%d",d);
       //printf("%d:\tmark= %d\tpre= %d\tval= %d\n",k,node[k].mark,node[k].pre,node[k].val);
    return 0;
}

Prim’s (MST) : Special Subtree C++ Solution

#include<bits/stdc++.h>
# define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> iPair;

class Graph{
	int V;
	list<iPair> *adj;
	public:
		Graph(int V);
		void addEdge(int u,int v,int w);
		void prim(int s);
};
Graph::Graph(int V){
	this->V = V;
	adj = new list<iPair>[V]; 
} 
void Graph::addEdge(int u,int v,int w){
	adj[v].push_back(make_pair(u,w));
	
	adj[u].push_back(make_pair(v,w));
}
void Graph::prim(int s){
	priority_queue< iPair, vector<iPair> , greater<iPair> > pq;
	vector<int> key(V,INF);
	vector<int> parent(V,-1);
	vector<bool> inMst(V,false);
	key[s]=0;
	pq.push(make_pair(key[s],s));
	while(!pq.empty()){
		int u = pq.top().second;
		pq.pop();
		inMst[u]=true;
		list<iPair>::iterator i;
		for(i = adj[u].begin();i!=adj[u].end();i++){
			int v = (*i).first;
			int w = (*i).second;
			if(!inMst[v]&&key[v]>w){
				parent[v]=u;
				key[v]=w;
				pq.push(make_pair(key[v],v));
			}
		}
	}
    int count=0;
	for(int i=1;i<V;i++){
		if(parent[i]!=-1){
			count+=key[i];
            //cout<<parent[i]<<"---"<<i<<endl;
		}
	}
    cout<<count<<endl;
}

int main(){
        int N,M,x,y,w,S;
        cin>>N>>M;
        Graph g(N+1);
        for(int i=0;i<M;i++){
            cin>>x>>y>>w;
            g.addEdge(x,y,w);
        }
        cin>>S;
        g.prim(S);
    return 0;
	
}

Prim’s (MST) : Special Subtree C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    public class Edge {
        public int D, W;
        public Edge(int dest, int weight) { D = dest; W = weight; }
        public Edge N;
    }
    public static Edge R = null;

    public static void Add(Edge e) {
        if(R == null) {
            R = e;
        } else if(e.W < R.W) {
            e.N = R;
            R= e;
        } else {
            Edge x = R;
            while(x.N != null && x.N.W < e.W) {
                x = x.N;
            }
            e.N = x.N;
            x.N = e;
        }
    }
    
    static void Main(String[] args) {
            string[] line = Console.ReadLine().Split(' ');
            int N = Int32.Parse(line[0]);
            int M = Int32.Parse(line[1]);
            List<Edge>[] edges = new List<Edge>[N+1];
            for(int n=1; n<N+1; n++) { edges[n] = new List<Edge>(); }
            for(int m=0; m<M; m++) {
                line = Console.ReadLine().Split(' ' );
                int x = Int32.Parse(line[0]);
                int y = Int32.Parse(line[1]);
                int w = Int32.Parse(line[2]);
                edges[x].Add(new Edge(y,w));
                edges[y].Add(new Edge(x,w));
            }
            int S = Int32.Parse(Console.ReadLine());
            foreach(Edge e in edges[S]) {
                Add(e);
            }
            bool[] done = new bool[N+1];
            done[S] = true;
            int cnt = 1;
            int sum = 0;
            while(cnt < N && R != null) {
                Edge e = R;
                R = e.N;
                if(!done[e.D]) {
                    sum += e.W;
                    done[e.D] = true;
                    cnt++;
                    foreach(Edge ee in edges[e.D]) {
                        if(!done[ee.D]) Add(ee);
                    }
                }
            }
            Console.WriteLine(sum);
    }
}

Prim’s (MST) : Special Subtree Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
 
class Cost implements Comparable<Cost> {
    public int r, v;
    public Cost(int cost, int vertex) {
        r = cost;
        v = vertex;
    }
    @Override
    public int compareTo(Cost c) {
        if (r < c.r) return -1;
        if (r> c.r) return 1;
        if (v < c.v) return -1;
        if (v > c.v) return 1;
        return 0;
    }
}
 
 
class Result {
 
    /*
     * Complete the 'prims' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. 2D_INTEGER_ARRAY edges
     *  3. INTEGER start
     */
     
     
     // Slide mst.p52
     public static boolean[] marked;
     public static PriorityQueue<Cost> pq;
     public static List<Cost> mstCosts;
     
    public static void visit(List<List<Cost>> danhsachlienke, int v) {
        marked[v] = true;
        for(Cost cost : danhsachlienke.get(v)) {
            if (!marked[cost.v]) {
                pq.add(cost);
            }
        }
    }
 
    public static int prims(int n, List<List<Integer>> edges, int start) {
        List<List<Cost>> danhsachlienke = new ArrayList<>(n + 1);
        pq = new PriorityQueue<Cost>();
        marked = new boolean[n+1];
        mstCosts = new ArrayList<Cost>();
        
        for(int i = 0; i < n + 1; ++i) {
            danhsachlienke.add(new ArrayList<Cost>());
        }
        
        for (List<Integer> edge : edges) {
            // System.out.println(edge.get(0) + " " + edge.get(1) + " " + edge.get(2));
            danhsachlienke.get(edge.get(0)).add(new Cost(edge.get(2), edge.get(1)));
            danhsachlienke.get(edge.get(1)).add(new Cost(edge.get(2), edge.get(0)));
        }
        
        visit(danhsachlienke, start);
        
        // mstCosts.size() == mstEdges.size()
        while (!pq.isEmpty() && mstCosts.size() < n - 1) {
            Cost cost = pq.poll();
            if (marked[cost.v]) {
                continue;
            } else {
                mstCosts.add(cost);
                visit(danhsachlienke, cost.v);
            }
        }
        
        int total = 0;
        for (Cost cost : mstCosts) {
            total += cost.r;
        }
        return total;
    }
 
}
 
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
 
        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
 
        int n = Integer.parseInt(firstMultipleInput[0]);
 
        int m = Integer.parseInt(firstMultipleInput[1]);
 
        List<List<Integer>> edges = new ArrayList<>();
 
        IntStream.range(0, m).forEach(i -> {
            try {
                edges.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                        .map(Integer::parseInt)
                        .collect(toList())
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });
 
        int start = Integer.parseInt(bufferedReader.readLine().trim());
 
        int result = Result.prims(n, edges, start);
 
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
 
        bufferedReader.close();
        bufferedWriter.close();
    }
}

Prim’s (MST) : Special Subtree JavaScript Solution


function calc(graph, edges, s) {
    var total = 0;
    var tree = [];
    tree[s] = [];
    while(true) {
        var min = [-1, -1, 1000000];
        for(var i=0; i<edges.length; i++) {
            if(tree[edges[i][0]] && !tree[edges[i][1]] && edges[i][2] <= min[2]) 
                min = edges[i];
        }
        if(min[0] == -1) return total;
        //console.log(min[0], min[1], min[2]);
        tree[min[0]].push([min[1], min[2]]);
        tree[min[1]] = [];
        total += min[2];
    }
}

function processData(input) {
    var lines = input.split('\n');
    var index = 0;
    var tokens = lines[index++].split(' ');
    var N = parseInt(tokens[0]);
    var M = parseInt(tokens[1]);
    var graph = [];
    for(var i=0; i<=N; i++) graph[i] = [];
    var edges = [];
    for(var j = 0; j < M; j++) {
        var tokens = lines[index++].split(' ');
        var a = parseInt(tokens[0]);
        var b = parseInt(tokens[1]);
        var w = parseInt(tokens[2]);
        edges.push([a, b, w]);
        edges.push([b, a, w]);
        graph[a].push([b, w]);
        graph[b].push([a, w]);
    }
    var s = parseInt(lines[index++]);
    var total = calc(graph, edges, s);
    
    console.log(total);
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Prim’s (MST) : Special Subtree Python Solution

import operator
n, m = map(int, input().split())
edges = {}
for __ in range(0, m):
    x, y, r = map(int, input().split())
    x -= 1
    y -= 1
    x, y = min(x, y), max(x, y)
    if (x, y) in edges:
        edges[x, y] = min(edges[x, y], r)
    else:
        edges[x, y] = r
        
s = int(input()) - 1

trees = []
sorted_edges = sorted(edges.items(), key=operator.itemgetter(1), reverse=True)
s = 0
while len(sorted_edges) > 0:
    (x, y), r = sorted_edges.pop()
    ok = True
    xi = None
    yi = None
    for k in range(0, len(trees)):
        if x in trees[k] and y in trees[k]:
            ok = False
            break
        elif x in trees[k]:
            trees[k].add(y)
            xi = k
        elif y in trees[k]:
            trees[k].add(x)
            yi = k
            
    if ok:
        s += r
        if xi != None and yi != None:
            trees[xi] |= trees[yi]
            trees.pop(yi)
        elif xi != None:
            trees[xi].add(y)
        elif yi != None:
            trees[yi].add(x)
        else:
            trees.append({x, y})
print(s)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python