HackerRank Kruskal (MST): Really Special Subtree

Yashwant Parihar,

In this post, we will solve HackerRank Kruskal (MST): Really Special Subtree Problem Solution.

Given an undirected weighted connected graph, find the Really Special SubTree in it. The Really Special SubTree is defined as a subgraph consisting of all the nodes in the graph and:

  • There is only one exclusive path from a node to every other node.
  • The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
  • No cycles are formed

To create the Really Special SubTree, always pick the edge with smallest weight. Determine if including it will create a cycle. If so, ignore the edge. If there are edges of equal weight available:

  • Choose the edge that minimizes the sum u+v+wt where u and v are vertices and wt is the edge weight.
  • If there is still a collision, choose any of them. Print the overall weight of the tree formed using the rules.
    For example, given the following edges:
u	v	wt
1	2	2
2	3	3
3	1	5

First choose 1 → 2 at weight 2. Next choose 2 → 3 at weight 3. All nodes are connected without cycles for a total weight of 3+2 = 5.
Function Description
Complete the kruskals function in the editor below. It should return an integer that represents the total weight of the subtree formed. kruskals has the following parameters:

  • g_nodes: an integer that represents the number of nodes in the tree
  • g_from: an array of integers that represent beginning edge node numbers
  • g_to: an array of integers that represent ending edge node numbers
  • g_weight: an array of integers that represent the weights of each edge

Input Format
The first line has two space-separated integers g_nodes and g_edges, the number of nodes and edges in the graph.
The next g_edges lines each consist of three space-separated integers g_from, g_to and g_weight, where g_from and g to denote the two nodes between which the undirected edge exists and g_weight denotes the weight of that edge.

Output Format

Print a single integer denoting the total weight of the Really Special SubTree.

HackerRank Kruskal (MST): Really Special Subtree Problem Solution
HackerRank Kruskal (MST): Really Special Subtree Problem Solution

Kruskal (MST): Really Special Subtree C Solution

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

#define NEW(x) (x*)malloc(sizeof(x))

typedef struct heap_data_struct {
    void * data;
    void * priority;
} heap_data;

heap_data * init_heap_data(void * data, void * priority) {
    heap_data * ret_heap_data = NEW(heap_data);
    ret_heap_data->data = data;
    ret_heap_data->priority = priority;
    return ret_heap_data;
}

void kill_heap_data(heap_data * hd, int kill_data) {
    if(hd) {
        if(kill_data) {
            free(hd->data);
        }
        if(hd->priority) {
            free(hd->priority);
        }
        free(hd);
    }
}

typedef struct heap_struct {
    heap_data ** data_arr;
    int (*compare)(heap_data*, heap_data*);
    int size;
    int cur_capacity;
} heap;

heap * init_heap(int init_capacity, int (*c)(heap_data*,heap_data*)) {
    heap * ret_heap = NEW(heap);
    ret_heap->data_arr=(heap_data**)malloc(init_capacity*sizeof(heap_data*));
    ret_heap->compare = c;
    ret_heap->size=0;
    ret_heap->cur_capacity = init_capacity;
    return ret_heap;
}

int heap_parent_index(int index) {
    return index == 0 ? 0 : ((index - 1) >> 1);
}

int heap_leftchild_index(int index) {
    return (index << 1) + 1;
}

void bubble_up(heap * h, int index) {
    
    if(index) {
        heap_data * cur_data = h->data_arr[index];
        int pindex=heap_parent_index(index);
        heap_data * parent_data = h->data_arr[pindex];
        //fprintf(stderr, "\t\tcomparing current index %d with parent index %d\n", index, pindex);
        if(h->compare(cur_data, parent_data) < 0) {
            //fprintf(stderr, "\t\tmismatch detected, exchanging with parent\n");
            h->data_arr[pindex] = cur_data;
            h->data_arr[index] = parent_data;
            bubble_up(h, pindex);
        }
    }
    
}

void trickle_down(heap * h, int index) {
    
    if(index >= h->size - 1) {
        
        return;
    }
    
    heap_data * cur_data = h->data_arr[index];
    int max_child_index=heap_leftchild_index(index);
    if(max_child_index >= h->size) {
        
        return;
    }
    heap_data * max_child_data = h->data_arr[max_child_index];
    
    int rchild_index = max_child_index+1;
    if(rchild_index < h->size) {
        heap_data * rchild_data = h->data_arr[rchild_index];
        //fprintf(stderr, "\t\tcomparing left child index %d with right child index %d\n", max_child_index, rchild_index);
        if(h->compare(rchild_data, max_child_data) < 0) {
            //fprintf(stderr, "\t\trchild has higher priority, updating max child index\n");
            max_child_index = rchild_index;
            max_child_data = rchild_data;
        }
    }
    
    //fprintf(stderr, "\t\tcomparing current index %d with child index %d\n", index, rchild_index);
    if(h->compare(max_child_data, cur_data) < 0) {
        //fprintf(stderr, "\t\tmismatch detected, exchanging with child\n");
        h->data_arr[max_child_index]=cur_data;
        h->data_arr[index] = max_child_data;
        trickle_down(h, max_child_index);
    }
}

void heap_add(heap * h, void * data, void * priority) {
    
    // increase capacity if necessary
    if(h->size == h->cur_capacity) {
        h->cur_capacity *=2;
        h->data_arr = (heap_data**)realloc(h->data_arr, h->cur_capacity*sizeof(heap_data*));
    }
    
    h->data_arr[h->size] = init_heap_data(data, priority);
    bubble_up(h, h->size++);
}

void * heap_pop(heap * h, int index) {
    
    
    if(index >= h->size) {
        return NULL;
    }
    
    void * ret_data = h->data_arr[index]->data;
    
    kill_heap_data(h->data_arr[index],0);
    h->data_arr[index]=h->data_arr[--h->size];
    bubble_up(h, index);
    trickle_down(h, index);
    
    return ret_data;
}

void kill_heap(heap * h, int kill_data) {
    if(h) {
        
        // free heap data
        int i;
        for(i = 0; i < h->size; ++i) {
            kill_heap_data(h->data_arr[i], kill_data);
        }
        
        // free heap data array
        free(h->data_arr);
        
        // free heap
        free(h);
    }
}

/*
 * DLL STUFF
 */

typedef struct dll_node_struct {
    void * data;
    struct dll_node_struct * prev;
    struct dll_node_struct * next;
} dll_node;

dll_node * init_dll_node(void * init_data) {
    dll_node * ret_node=NEW(dll_node);
    ret_node->data = init_data;
    ret_node->prev = ret_node->next = NULL;
    return ret_node;
}

void kill_dll_node(dll_node * n, int kill_data) {
    if(n) {
        if(kill_data) {
            free(n->data);
        }
        free(n);
    }
}

typedef struct dll_struct {
    dll_node * head;
    dll_node * tail;
    int len;
} dll;

dll * init_dll() {
    dll * ret_dll = NEW(dll);
    ret_dll->head = init_dll_node(NULL);
    ret_dll->tail = init_dll_node(NULL);
    ret_dll->head->next = ret_dll->tail;
    ret_dll->tail->prev = ret_dll->head;
    return ret_dll;
}

void dll_append(dll * l, void * data) {

    dll_node * new_last = init_dll_node(data);
    new_last->next = l->tail;
    new_last->prev = l->tail->prev;
    l->tail->prev = new_last;
    new_last->prev->next = new_last;

}

void kill_dll(dll * l, int kill_data) {
    if(l) {
        dll_node * cur_node = l->head->next;
        
        // free data nodes
        while(cur_node != l->tail) {
            dll_node * next_node = cur_node->next;
            kill_dll_node(cur_node, kill_data);
            cur_node = next_node;
        }
        
        // free head and tail
        free(l->head);
        free(l->tail);
        
        // free dll
        free(l);
    }
}


/*
 *  GRAPH STUFF
 */

struct adj_graph_node_struct;

typedef struct adj_graph_edge_struct {
    struct adj_graph_node_struct * neighbor;
    int weight;
} adj_graph_edge;

typedef struct adj_graph_node_struct {
    int id;
    dll * edges;
} adj_graph_node;

adj_graph_node * init_adj_graph_node(int id) {
    adj_graph_node * ret_node = (adj_graph_node*)malloc(sizeof(adj_graph_node));
    ret_node->id = id;
    ret_node->edges = init_dll();
    return ret_node;
}

adj_graph_edge * init_adj_graph_edge(adj_graph_node * neighbor, int weight) {
    adj_graph_edge * ret_edge = NEW(adj_graph_edge);
    ret_edge->weight = weight;
    ret_edge->neighbor = neighbor;
    return ret_edge;
}

void add_edge_to_node(adj_graph_node * from, adj_graph_node * to, int weight) {

    dll_append(from->edges, init_adj_graph_edge(to, weight));

}

void kill_adj_graph_edge(adj_graph_edge * e) {
    if(e) {
        free(e);
    }
}

void kill_adj_graph_node(adj_graph_node * n) {
    if(n) {
        
        // destroy list of edges, and edges also
        kill_dll(n->edges, 1);
        
        // free n
        free(n);
    }
}

typedef struct adj_graph_struct {
    int num_nodes;
    adj_graph_node ** nodes;
} adj_graph;

adj_graph * init_adj_graph(int node_count) {
    adj_graph * ret_graph = NEW(adj_graph);
    ret_graph->num_nodes=node_count;
    ret_graph->nodes = (adj_graph_node**)malloc(node_count*sizeof(adj_graph_node*));
    int i;
    for(i = 0; i < node_count; ++i) {
        ret_graph->nodes[i] = init_adj_graph_node(i);
    }
    return ret_graph;
}

void kill_graph(adj_graph * g) {
    if(g) {
        int i;
        for(i = 0; i < g->num_nodes; ++i) {
            kill_adj_graph_node(g->nodes[i]);
        }
        free(g->nodes);
        free(g);
    }
}

void print_edge(adj_graph_edge * e) {
    fprintf(stderr, "\t\t\tneighbor node: %d, weight: %d\n", e->neighbor->id, e->weight);
}

int compare_edges(heap_data * h1, heap_data * h2) {
    //print_edge((adj_graph_edge*)h1->data);
    //print_edge((adj_graph_edge*)h2->data);
    return ((adj_graph_edge*)h1->data)->weight - ((adj_graph_edge*)h2->data)->weight;
}

void update_frontier(heap * f, adj_graph_edge * d, char * visited) {
    
    adj_graph_node * e = d->neighbor;
    //fprintf(stderr, "added node %d, edge weight %d\n", e->id, d->weight);
    
    dll_node * cur_node;
    dll * edge_list = e->edges;
    for(cur_node = edge_list->head->next; cur_node != edge_list->tail; cur_node = cur_node->next) {
        adj_graph_edge * cur_edge = (adj_graph_edge*)cur_node->data;
        if(visited[cur_edge->neighbor->id] == 0) {
            //fprintf(stderr, "\tneighbor %d not visited, added edge of weight %d to heap\n", cur_edge->neighbor->id, cur_edge->weight);
            heap_add(f, cur_edge, NULL);
        }
    }
}

int main() {

    // read N, M
    int num_nodes, num_edges;
    scanf("%d", &num_nodes);
    scanf("%d", &num_edges);
    
    // initialize
    adj_graph * g = init_adj_graph(num_nodes);
    
    // read edges
    // initialize edge_weight pre-processor
    int ** edge_weights = (int**)malloc(num_nodes*sizeof(int*));
    int i, j;
    for(i=0; i < num_nodes; ++i) {
        edge_weights[i] = (int*)malloc(num_nodes*sizeof(int));
        for(j=0; j < num_nodes; ++j) {
            edge_weights[i][j] = -1;
        }
    }
    //fprintf(stderr, "checkpoint\n");
    
    // find minimum length edge between appropriate nodes
    for(i = 0; i < num_edges; ++i) {
        int n1, n2, w;
        scanf("%d",&n1);
        //fprintf(stderr, "n1: %d ", n1);
        scanf("%d",&n2);
        //fprintf(stderr, "n2: %d ", n2);
        scanf("%d",&w);
        //fprintf(stderr, "w: %d\n", w);
        
        // array is 0-indexed
        --n1;
        --n2;
        if(edge_weights[n1][n2] < 0 || w < edge_weights[n1][n2]) {
            edge_weights[n1][n2] = w;
            edge_weights[n2][n1] = w;
        }
    }
    //fprintf(stderr, "checkpoint\n");
    
    // initialize graph nodes
    for(i = 0; i < num_nodes; ++i) {
        for(j = 0; j < num_nodes; ++j) {
            if(edge_weights[i][j] > -1) {
                add_edge_to_node(g->nodes[i], g->nodes[j], edge_weights[i][j]);
            }
        }
    }
    
    //fprintf(stderr, "checkpoint\n");
    
    // don't need edge weights anymore, so free
    for(i = 0; i < num_nodes; ++i) {
        free(edge_weights[i]);
    }
    free(edge_weights);
    
    char * visited = (char*)calloc(num_nodes, sizeof(char));
    int start_node;
    scanf("%d", &start_node);
    --start_node;
    heap * frontier = init_heap(num_nodes, &compare_edges);
    heap_add(frontier, init_adj_graph_edge(g->nodes[start_node], 0), NULL);
    
    // solve problem
    int mst_weight = 0;
    int num_visited = 0;
    while(num_visited < num_nodes) {
        adj_graph_edge * next_edge = (adj_graph_edge*)heap_pop(frontier, 0);
        if(visited[next_edge->neighbor->id] == 0) {
            visited[next_edge->neighbor->id] = (char)1;
            ++num_visited;
            mst_weight+=next_edge->weight;
            update_frontier(frontier, next_edge, visited);
        }
    }
    
    // print solution
    printf("%d\n", mst_weight);
    
    // clean up
    kill_heap(frontier, 0);
    kill_graph(g);
    
    return 0;
}

Kruskal (MST): Really Special Subtree C Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

typedef struct Edge {

	int A;
	int B;
	int weight;

	Edge(int a, int b, int w) {
		A = a;
		B = b;
		weight = w;
	}

	bool operator<(const Edge& other) const
	{
		return weight > other.weight;
	}
}Edge;

priority_queue<Edge> edges;
vector<int> subTreeIndex;

bool IsNewSubTree(Edge edge) {
	return subTreeIndex[edge.A] == 0 && subTreeIndex[edge.B] == 0;
}

bool IsSameSubTree(Edge edge) {
	return subTreeIndex[edge.A] == subTreeIndex[edge.B];
}

bool IsNewNode(Edge edge) {
	return subTreeIndex[edge.A] == 0 || subTreeIndex[edge.B] == 0;
}

void CreateNewSubTree(Edge edge, int treeIndex) {
	subTreeIndex[edge.A] = treeIndex;
	subTreeIndex[edge.B] = treeIndex;
}

void AddToSubTree(Edge edge) {
	if (subTreeIndex[edge.A] == 0) {
		subTreeIndex[edge.A] = subTreeIndex[edge.B];
	}
	else {
		subTreeIndex[edge.B] = subTreeIndex[edge.A];
	}
}

void MergeSubTrees(Edge edge) {
	int subTreeIndexToKeep = subTreeIndex[edge.A];
	int subTreeIndexToDiscard = subTreeIndex[edge.B];
	for (int i = 0; i < subTreeIndex.size(); i++)
	{
		if (subTreeIndex[i] == subTreeIndexToDiscard) {
			subTreeIndex[i] = subTreeIndexToKeep;
		}
	}
}



int main() {

	int nNodes, nEdges, nodeA, nodeB, weight, start, c, totalWeight, nodesCount;
	cin >> nNodes >> nEdges;

	subTreeIndex = vector<int>(nNodes, 0);
	edges = priority_queue<Edge>();

	for (int i = 0; i < nEdges; i++)
	{
		cin >> nodeA >> nodeB >> weight;
		nodeA--; nodeB--;
	    edges.push(Edge(nodeA, nodeB, weight));
	}
	cin >> start;
	c = 1;
	totalWeight = 0;

	while (!edges.empty()) {
		Edge edge = edges.top();
		if (IsNewSubTree(edge)) {
			c++;
			CreateNewSubTree(edge, c);
			totalWeight += edge.weight;
		}
		else if (!IsSameSubTree(edge)) {
			if (IsNewNode(edge)) {
				AddToSubTree(edge);
			}
			else {
				MergeSubTrees(edge);
			}
			totalWeight += edge.weight;
		}
		edges.pop();
	}

	cout << totalWeight << endl;
	return EXIT_SUCCESS;
}

Kruskal (MST): Really Special Subtree C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    class Edge {
        public int n1 { get; set; }
        public int n2 { get; set; }
        public int distance { get; set; }
    }
    class Node {
        public bool visited { get; set; }
        public int distance { get; set; }
        public List<Edge> edges { get; set;}
    }
    
    static void Test() {
        string[] line = Console.ReadLine().Split(' ');
        int nodeCount = Convert.ToInt32(line[0]);
        int edgeCount = Convert.ToInt32(line[1]);
        
        Node[] nodes = new Node[nodeCount];
        for( int i = 0; i < nodeCount; i++ ) {
            Node node = new Node();
            node.distance = int.MaxValue;
            node.edges = new List<Edge>();
            nodes[i] = node;
        }
        
        for( int i = 0; i < edgeCount; i++ ) {
            line = Console.ReadLine().Split(' ');
            int n1 = Convert.ToInt32(line[0]) - 1;
            int n2 = Convert.ToInt32(line[1]) - 1;
            int d = Convert.ToInt32(line[2]);
            Edge edge = new Edge();
            edge.n1 = n1;
            edge.n2 = n2;
            edge.distance = d;
            nodes[n1].edges.Add(edge);
            edge = new Edge();
            edge.n1 = n2;
            edge.n2 = n1;
            edge.distance = d;
            nodes[n2].edges.Add(edge);
        }
                
        int start = Convert.ToInt32(Console.ReadLine()) - 1;
        nodes[start].distance = 0;
        
        while(true) {
            int nextNode = -1;
            int nextDistance = int.MaxValue;
            for( int i = 0; i < nodeCount; i++ ) {
                if( !nodes[i].visited && nodes[i].distance < nextDistance) {
                    nextNode = i;
                    nextDistance = nodes[i].distance;
                }
            }
            if( nextDistance == int.MaxValue) {
                break;
            }
            
            nodes[nextNode].visited = true;
            foreach(var e in nodes[nextNode].edges) {
                if( !nodes[e.n2].visited ) {
                    nodes[e.n2].distance = Math.Min(nodes[e.n2].distance, e.distance);
                }
            }
        }
        
        
        int sum = 0;
        for( int i = 0; i < nodeCount; i++ ) {
            sum += nodes[i].distance;
        }
        Console.WriteLine(sum);
    }
    
    static void Main(String[] args) {
        //int count = Convert.ToInt32(Console.ReadLine());
        //for( int i = 0; i < count; i++) {
            Test();
        //}        
    }
}

Kruskal (MST): Really Special Subtree Java Solution

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Kruskal_MST_Really_Special_Subtree {
    static class Edge implements Comparable<Edge> {
        int v, w, weight;

        public Edge(int v, int w, int weight) {
            this.v = v;
            this.w = w;
            this.weight = weight;
        }

        public int from() {
            return v;
        }

        public int to() {
            return w;
        }

        public int weight() {
            return weight;
        }

        @Override
        public int compareTo(Edge that) {
            if (weight == that.weight) {
                if (v == that.v) return Integer.compare(w, that.w);
                return Integer.compare(v, that.v);
            }
            return Integer.compare(weight, that.weight);
        }
    }

    
    static Set<Edge> edges = new TreeSet<>();
    static int[] id;
    static int[] size;

    static int find(int i) {
        while (i != id[i]) i = id[i];
        return i;
    }

    static void union(int v, int w) {
        int i = find(v);
        int j = find(w);
        if (size[i] < size[j]) {
            id[i] = j;
            size[j] += size[i];
        } else {
            id[j] = id[i];
            size[i] += size[j];
        }
    }

    static boolean connected(int v, int w) {
        return find(v) == find(w);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt(), E = sc.nextInt();

        // init
        id = new int[V + 1];
        size = new int[V + 1];
        for (int i = 0; i <= V; i++) id[i] = i;
        // List<Edge> graph = new ArrayList<>(); 

        // add edge
        for (int i = 0; i < E; i++) {
            int v = sc.nextInt(), w = sc.nextInt(), weight = sc.nextInt();
            edges.add(new Edge(Math.min(v, w), Math.max(v, w), weight));
        }

        // solve: cal weightMST
        int weightMST = 0;
        for (Edge e : edges) {
            if (!connected(e.v, e.w)) {
                union(e.v, e.w);
                weightMST += e.weight;
            }
        }
        System.out.println(weightMST);
    }
}

Kruskal (MST): Really Special Subtree JavaScript Solution

function findRoot(dSet, node){
    if(node === dSet[node]){
        return node;
    }
    return findRoot(dSet, dSet[node]);
}

function totalValue(edge){
    return edge.weight + edge.from + edge.to;
}

function processData(input) {
    input = input.split('\n');
    let [n, m] = input[0].split(' ').map(Number);
    
    // load graph
    let edgesArr = [];
    for(let i = 1; i <= m; i++){
        let [from, to, weight] = input[i].split(' ').map(Number);
        from--; to--;
        // loop
        if(from === to){
            continue;
        }
        
        edgesArr.push({
            from,
            to,
            weight
        });
    }
    // console.log(JSON.stringify(edgesArr));
    // group and sort
    let grouped = edgesArr.reduce((rv, e) => {
        (rv[e.weight] = rv[e.weight] || []).push(e);
        return rv;
    }, {});
    edgesArr = [];
    let keys  = Object.keys(grouped);
    keys.sort((a, b) => a-b);
    for(let i = 0; i < keys.length; i++){
        grouped[keys[i]].sort((a,b) => totalValue(a) - totalValue(b));
        edgesArr.push(...grouped[keys[i]]);
    }
    // console.log(JSON.stringify(edgesArr));
    
    // calc mst
    let mst = [];
    let totalWeight = 0;
    let dSet = Array(n).fill(null).map((x,i) => i);
    
    for(let i = 0; i < edgesArr.length; i++){
        let e = edgesArr[i];
        if(e === undefined) continue;
        
        let fRoot = findRoot(dSet, e.from);
        let tRoot = findRoot(dSet, e.to);
        if(fRoot === tRoot){
            continue; // same graph
        }
        
        dSet[fRoot] = tRoot;
        mst.push(e);
        totalWeight += e.weight;
    }
    // console.log(mst);
    console.log(totalWeight);
} 

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

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

Kruskal (MST): Really Special Subtree Python Solution

class edge(object):
    def __init__(self,a,b,c):
        self.a=a
        self.b=b
        self.w=c
class Unionfind(object):
   
    def __init__(self):
        self.leader = {}  # maps member to group leader
        self.group = {}   # maps group leader to set of members
 
    def makeSet(self, e):
        group = set(e)
        self.group[e[0]] = group
        for i in group:
            self.leader[i] = e[0]

    def getNumGroups(self):
        """Return the number of groups"""
        return len(self.group)

    def find(self,e):
        return self.leader[e]

    def union(self,a,b):
        l1=self.leader[a]
        l2=self.leader[b]
        if(l1!=l2):
            g1=self.group[l1]
            g2=self.group[l2]
            g1|=g2
            del self.group[l2]
            for i in g2:
                self.leader[i]=l1

n,m=map(int,input().split())
listed=[]
u=Unionfind()
for i in range(m):
    a,b,c=map(int,input().split())
    e=edge(a,b,c)
    listed.append(e)
s=0
for i in range(n): u.makeSet([i+1])
listed.sort(key=lambda x: (x.w,x.a+x.b+x.w))
for i in listed:
    if u.find(i.a)!=u.find(i.b):
        u.union(i.a,i.b)
        s+=i.w
print (s)
c C# C++ HackerRank Solutions java javascript python

Leave a Reply