HackerRank Prim’s (MST): Special Subtree problem solution

In this HackerRank Prim’s (MST): Special Subtree problem solution, given a graph that consists of several edges connecting its nodes, find a subgraph of the given graph with the following properties:

1. The subgraph contains all the nodes present in the original graph.
2. The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
3. 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.

HackerRank Prim’s (MST): Special Subtree problem solution in Python.

N, E = map(int, input().split())

edges = [[] for i in range(N + 1)]

for e in range(E):
    x, y, r = map(int, input().split())
    edges[x].append((y, r))
    edges[y].append((x, r))                      

S = {x + 1 for x in range(N)}
T = set()
E = 0;

T.add(S.pop())
    
#print(sorted(edges, key = lambda x: x[2]))
while S:
       
    minStart = -1;
    minEnd = -1;
    minCost = float("inf");
    
    for v in T:
        for e in edges[v]:            
            if e[0] in S:
                if e[1] < minCost:
                    minStart = v
                    minEnd = e[0]
                    minCost = e[1]
                    
    if minCost < float("inf"):
        E += minCost
        S.remove(minEnd)
        T.add(minEnd)
        
print(E)

Prim’s (MST): Special Subtree problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    static int[] distances;
    static int[][] matrix;
    static Set<Integer> visited;
    static boolean[] vis;
    static int minEdge;
    static int min = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int nodesCount = scanner.nextInt();
        matrix = new int[nodesCount + 1][nodesCount + 1];
        int edgesCount = scanner.nextInt();
        visited = new HashSet<>();
        vis = new boolean[nodesCount + 1];
        for (int i = 0; i < edgesCount; i++) {
            int source = scanner.nextInt();
            int target = scanner.nextInt();
            int weight = scanner.nextInt();
            matrix[source][target] = weight == 0 ? -1 : weight;
            matrix[target][source] = weight == 0 ? -1 : weight;
        }
        int start = scanner.nextInt();
        visited.add(start);
        vis[start] = true;
        long sum = 0;
        while (visited.size() != nodesCount) {
            minEdge = 0;
            min = Integer.MAX_VALUE;

            for (Integer in : visited) {

                getNeighbours(in);
            }

            if (min == -1) {
                min = 0;
            }
            sum += min;

            visited.add(minEdge);
            vis[minEdge] = true;

        }
        System.out.println(sum);
    }

    static void getNeighbours(int node) {
        for (int in = 0; in < matrix[node].length; in++) {
            if (in != 0 && in != node) {
                if (!vis[in] && matrix[node][in] != 0) {
                    if (min > matrix[node][in]) {
                        minEdge = in;
                        min = matrix[node][in];
                        if (matrix[node][in] == -1) {
                            break;
                        }
                    }
                }
            }
        }
    }
}

Problem solution in C++.

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stdbool.h>

using namespace std;

#define MAX_N 3000

struct edge {
	int from;
	int to;
	int w;

	bool operator<(const edge& rhs) const
	{
		return w > rhs.w;
	}
};

int index[MAX_N];

bool djsInSameSet(int a, int b) {
	return index[a] == index[b];
}

void djsInit(int n) {
	for (int i = 0; i < n; i++) {
		index[i] = i;
	}
}

void djsUnion(int a, int b, int n) {
	int va = index[a];
	int vb = index[b];
	for (int i = 0; i < n; i++) {
		if (index[i] == va) {
			index[i] = vb;
		}
	}
}

priority_queue<edge> pq;

int main() {
	int N, M;
	scanf("%d %d", &N, &M);

	djsInit(N);
	
	for (int i = 0; i < M; i++) {
		int f, t, w;
		scanf("%d %d %d", &f, &t, &w);
		
		f-=1;
		t-=1;
		
		edge e;
		e.to = t;
		e.from = f;
		e.w = w;
		
		pq.push(e);
	}
	
	int s;
	scanf("%d", &s);
	
	int size = 0;
	
	for (int i = 0; i < N - 1; i++) {
		edge ce;
		ce = pq.top();
		pq.pop();
		
		if (!djsInSameSet(ce.from, ce.to)) {
			djsUnion(ce.from, ce.to, N);
			size+=ce.w;
		} else {
			i--;
		}
	}
	
	printf("%d", size);
	
	return 0;
}

Problem solution in C.

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

int N, M;
int S = 0;
int graph[3001][3001];
long long sum = 0;
int visited_nodes[3001] = { 0 };
int no_visited_nodes = 0;

typedef struct {
    int len;
    short s;
    short e;
} vertex;

vertex vertex_heap[3001*3001];
int next_heap_index = 1;

int is_heap_empty()
{
    return (next_heap_index == 1);
}

void push_to_heap(vertex v)
{
    int i = next_heap_index;
    vertex_heap[i] = v;
    while(i > 1 && vertex_heap[i/2].len > vertex_heap[i].len)
    {
        vertex tmp = vertex_heap[i/2];
        vertex_heap[i/2] = vertex_heap[i];
        vertex_heap[i] = tmp;
        i /= 2; 
    }
    
    next_heap_index++;
}

vertex pop_from_heap()
{
    vertex ret = vertex_heap[1];
    vertex lower_elem = vertex_heap[next_heap_index-1];
    next_heap_index--;
    
    int i = 1;
        
    vertex_heap[i] = lower_elem;
    while(i < next_heap_index)
    {
        int li = 2*i;
        int ri = 2*i+1;
        int ex_index = 0;

        if(li < next_heap_index)
        {
            if(vertex_heap[li].len < vertex_heap[i].len)
            {
                ex_index = li;
            }
            
        }
        
        if(ri < next_heap_index)
        {
            if(vertex_heap[ri].len < vertex_heap[i].len &&
               (!ex_index || vertex_heap[ri].len < vertex_heap[li].len))
            {
                ex_index = ri;
            }
        }
        
        if(ex_index)
        {
            vertex tmp = vertex_heap[i];
            vertex_heap[i] = vertex_heap[ex_index];
            vertex_heap[ex_index] = tmp;
            i = ex_index;
        }
        else break;
    }
    
    return ret;
}

void push_all_vertex_edges(int s)
{
  //  printf("All edges for : %dn", s);
    for(int e = 1; e <= N; e++)
    {
        if(graph[s][e] != -1)
        {
            vertex v = { graph[s][e], s, e};
      //      printf("Pushing %d-%d (len: %d)n", s, e, graph[s][e]);
            push_to_heap(v);
        }
    }
}


int main() {
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            graph[i][j] = -1;
        
    for(int i = 1; i <= M; i++)
    {
        int i, j, k;
        scanf("%d %d %d", &i, &j, &k);
        graph[i][j] = k;    
        graph[j][i] = k;    
    }
    
    scanf("%d", &S);
    no_visited_nodes = 1;
    visited_nodes[S] = 1;
   //         printf("Visited node 1n");
    push_all_vertex_edges(S);
    
    while(no_visited_nodes < N)
    {
        vertex v = pop_from_heap();
        if(visited_nodes[v.e] == 0)
        {
            visited_nodes[v.e] = 1;
          //  printf("Visited node %dn", v.e);
            no_visited_nodes++;
            push_all_vertex_edges(v.e);
           // printf("! %d-%d (len: %d)n", v.s, v.e, v.len);
            sum += v.len;
        }
    }
    
    printf("%lldn", sum);
        
    return 0;
}