HackerRank Kruskal (MST): Really Special Subtree
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 5First 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.
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)
