HackerRank Prim’s (MST) : Special Subtree

Yashwant Parihar,

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

5 6
1 2 3
1 3 4
4 2 6
5 2 2
2 3 5
3 5 7
1

Sample Output 0

15

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

Leave a Reply

Your email address will not be published. Required fields are marked *