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:
- 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.
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)
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; }