HackerRank Matrix Problem Solution
In this post, we will solve HackerRank Matrix Problem Solution.
The kingdom of Zion has cities connected by bidirectional roads. There is a unique path between any pair of cities. Morpheus has found out that the machines are planning to destroy the whole kingdom. If two machines can join forces, they will attack. Neo has to destroy roads connecting cities with machines in order to stop them from joining forces. There must not be any path connecting two machines.
Each of the roads takes an amount of time to destroy, and only one can be worked on at a time. Given a list of edges and times, determine the minimum time to stop the attack. For example, there are n = 5 cities called 0-4. Three of them have machines and are colored red. The time to destroy is shown next to each road. If we cut the two green roads, there are no paths between any two machines. The time required is 3 + 2 = 5.
Function Description
Complete the function minTime in the editor below. It must return an integer representing the minimum time to cut off access between the machines. min Time has the following parameter(s):
roads: a two-dimensional array of integers, each roads[i] = [cityl, city2, time] where cities are connected by a road that takes time to destroy
machines: an array of integers representing cities with machines
Input Format
The first line of the input contains two space-separated integers, n and k, the number of cities and the number of machines.
Each of the following n – 1 lines contains three space-separated integers, cityl, city2, and time. There is a bidirectional road connecting cityl and city2, and to destroy this road it takes time units.
Each of the last k lines contains an integer, machine[i], the label of a city with a machine.
Output Format
Return an integer representing the minimum time required to disrupt the connections among all machines.
Sample Input
5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0
Sample Output
10
Matrix C Solution
#include <stdio.h>
#include <stdlib.h>
#define N 100001
int edge[N][3];
int *sedge[N];
int mach[N];
int un[N];
int uncnt[N];
int cmp(const void *p1, const void *p2) {
const int *a1=*((const int **)p1);
const int *a2=*((const int **)p2);
return a2[2]-a1[2];
}
int main(void) {
int n, k;
int i, m, u, v;
long t=0;
scanf("%d%d", &n, &k);
for (i=0; i<(n-1); i++) {
scanf("%d%d%d", edge[i], edge[i]+1, edge[i]+2);
sedge[i]=edge[i];
}
for (i=0; i<k; i++) {
scanf("%d", &m);
mach[m]=1;
}
qsort(sedge, n-1, sizeof(sedge[0]), cmp);
for (i=1; i<=n; i++) {
un[i]=i;
uncnt[i]=1;
}
for (i=0; i<(n-1); i++) {
for (u=sedge[i][0]; u!=un[u]; u=un[u]);
for (v=sedge[i][1]; v!=un[v]; v=un[v]);
if (mach[u] && mach[v]) {
t+=sedge[i][2];
} else {
if (uncnt[u]<uncnt[v]) {
uncnt[v]+=uncnt[u];
un[u]=un[v];
} else {
uncnt[u]+=uncnt[v];
un[v]=un[u];
}
mach[u]|=mach[v];
mach[v]|=mach[u];
}
}
printf("%ld\n", t);
return 0;
}Matrix C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <limits>
#include <stack>
using namespace std;
struct Edge
{
int f = -1;
int t = -1;
int c = -1;
Edge(int from, int to, int cost) : f(from), t(to), c(cost) {};
};
struct Node
{
set<int> nedges;
bool hasMach = false;
};
int splits = 0;
long totalcost = 0;
vector<Node> nodes;
vector<Edge> edges;
vector<int> mach;
stack<int> st;
set<int> visited;
int DFS(int root)
{
if (nodes[root].nedges.size() == 0)
return 0;
if (nodes[root].hasMach) //Hit a machine?
{
splits++;
return st.top(); //Return Edge to delete
}
int rv = 0;
visited.insert(root);
for (auto i : nodes[root].nedges)
{
int to = edges[i].f + edges[i].t - root;
if (visited.find(to) == visited.end())
{
if (edges[i].c < edges[st.top()].c) //If equal or lower than last best edge
st.push(i); //Add to stack
rv = DFS(to); //Recurse this child
if (rv != 0) //Something significant returned
{
if (rv == i) //This is the edge to delete
{
// splits++;
totalcost += edges[i].c;
nodes[edges[i].t].nedges.erase(i);
nodes[edges[i].f].nedges.erase(i);
st.pop();
rv = 0; //Reset delete indicator
// However keep processing siblings and nieces
}
else
break; //Don't keep processing siblings
//Move out to edge to delete
}
else //Return value is zero so remove top stack element if it is this one
{
if (st.top() == i)
st.pop();
}
}
}
visited.erase(root);
return rv;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int N, K;
cin >> N >> K;
nodes.resize(N);
mach.resize(K);
edges.push_back(Edge(-1,-1,numeric_limits<int>::max()));
int x,y,z;
for (int i = 1; i < N; i++) //Roads
{
cin >> x >> y >> z;
edges.push_back(Edge(x,y,z));
nodes[x].nedges.insert(i);
nodes[y].nedges.insert(i);
}
int c;
for (int i = 0; i < K; i++)
{
cin >> mach[i];
nodes[mach[i]].hasMach = true;
}
for (int cm = 0; cm < mach.size(); cm++)
{
visited.clear();
while (!st.empty())
st.pop();
st.push(0); //Store limit edge in stack to simplify dfs
nodes[mach[cm]].hasMach = false; //Remove mark to make DFS simpler
int dfsres = DFS(mach[cm]); //Ignore return value here
nodes[mach[cm]].hasMach = true; //Reinstate mark -->> probably unnecesary
if (splits == K-1)
break;
}
cout << totalcost << endl;
return 0;
}Matrix C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(String[] args) {
string[] tokens_n = Console.ReadLine().Split(' ');
int n = Convert.ToInt32(tokens_n[0]);
int k = Convert.ToInt32(tokens_n[1]);
var edges = new List<Edge>();
for(int a0 = 0; a0 < n-1; a0++){
string[] tokens_x = Console.ReadLine().Split(' ');
int x = Convert.ToInt32(tokens_x[0]);
int y = Convert.ToInt32(tokens_x[1]);
int z = Convert.ToInt32(tokens_x[2]);
edges.Add(new Edge() { Value = z, To = x, From = y});
}
edges = edges.OrderByDescending(c => c.Value).ToList();
var nodesToDisconnect = new HashSet<int>();
for(int a0 = 0; a0 < k; a0++){
int m = Convert.ToInt32(Console.ReadLine());
nodesToDisconnect.Add(m);
}
var result = GetMinToDisconnectEdgeSum(edges, nodesToDisconnect);
Console.WriteLine(result);
}
static long GetMinToDisconnectEdgeSum(List<Edge> edges, HashSet<int> nodesToDisconnect){
var result = 0;
var nodeSet = new DisjointSet(nodesToDisconnect);
for(var i = 0; i < edges.Count; i++){
var currentEdge = edges[i];
nodeSet.MakeSet(currentEdge.To);
nodeSet.MakeSet(currentEdge.From);
if(nodeSet.HasMachine(currentEdge.To) && nodeSet.HasMachine(currentEdge.From)){
result += currentEdge.Value;
}
else{
nodeSet.Union(currentEdge.To, currentEdge.From);
}
}
return result;
}
public class DisjointSet{
private Dictionary<int, int> sets;
private HashSet<int> setsWithMachines;
public DisjointSet(HashSet<int> machines){
this.sets = new Dictionary<int, int>();
this.setsWithMachines = machines;
}
public bool MakeSet(int setMember){
if(sets.ContainsKey(setMember)){
return false;
}
sets.Add(setMember, -1);
return true;
}
public int FindSet(int setMember){
if(!sets.ContainsKey(setMember)){
return -1;
}
var partOfSet = sets[setMember];
if(partOfSet == -1){
return setMember;
}
return FindSet(partOfSet);
}
public void Union(int setMember1, int setMember2){
MakeSet(setMember1);
MakeSet(setMember2);
var partOfSet1 = FindSet(setMember1);
var partOfSet2 = FindSet(setMember2);
sets[partOfSet1] = partOfSet2;
if(setsWithMachines.Contains(setMember1) || setsWithMachines.Contains(setMember2) || setsWithMachines.Contains(partOfSet1)){
setsWithMachines.Add(partOfSet2);
}
}
public bool HasMachine(int setMember){
var partOfSet = FindSet(setMember);
return setsWithMachines.Contains(partOfSet);
}
}
public class Edge{
public int Value { get; set; }
public int From { get; set; }
public int To { get; set; }
}
}Matrix Java Solution
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
class Forest{
public static final int CITYNODE = 1;
public static final int MACHINENODE = 2;
int[] elements;
int[] sizes;
int[] parent;
int sz;
public Forest(int n){
sz = n;
elements = new int[n];
parent = new int[n];
sizes = new int[n];
Arrays.fill(elements, CITYNODE);
Arrays.fill(sizes,1);
//Arrays.fill(parent, -1);
for(int i = 0; i < n; i++){
parent[i] = i;
}
}
public void toggleToMachineNode(int idx){
elements[idx] = MACHINENODE;
}
public boolean hasMachine(int idx){
if(idx < 0 || idx >= sz) return false;
if(parent[idx] == idx) return elements[idx] == MACHINENODE;
return hasMachine(parent[idx]);
}
public int find(int q){
if(q < 0 || q >= sz) return -1;
if(parent[q] == q) return q;
return find(parent[q]);
}
public void union(int q, int r){//by size
q = find(q); // qs parent
r = find(r); // rs parent
if(q == r) return;
if(sizes[q] < sizes[r]){
//swap
int t = q; q = r; r = t;
}
if(hasMachine(q) || hasMachine(r)){
toggleToMachineNode(q);
toggleToMachineNode(r);
}
parent[r] = q;
sizes[q] += sizes[r];
return;
}
}
class Road implements Comparable{
int c1, c2;
Integer t;
public Road(int city1, int city2, int time){
c1 = city1; c2 = city2; t = time;
}
@Override
public int compareTo(Object o) {
Road other = (Road)o;
return t.compareTo(other.t);
}
@Override
public String toString() {
return "Road [c1=" + c1 + ", c2=" + c2 + ", t=" + t + "]";
}
}
class Result{
public static int solve(int n, int k, List<Integer> machines, List<Road> roads, Forest forest){
int result = 0;
Collections.sort(roads, Collections.reverseOrder());
for(Road rd: roads){
//System.out.println("Processing road: " + rd);
if(forest.hasMachine(rd.c1) && forest.hasMachine(rd.c2)) {
result = result + rd.t;
}else{
forest.union(rd.c1, rd.c2);
}
}
return result;
}
}
public class Solution {
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] nk = br.readLine().trim().split(" ");
int n = Integer.parseInt(nk[0]), k = Integer.parseInt(nk[1]);
Forest forest = new Forest(n);
List<Integer> machines = new ArrayList<>();
List<Road> roads = new ArrayList<>();
for (int line = 1; line <= n - 1; line++) {
String[] city1City2Time = br.readLine().trim().split(" ");
//HACKERRANKs wrong input case, they have abandoned this free platform :(
if(city1City2Time[0].equals("a")) continue;
// .....................................................................
int city1 = Integer.parseInt(city1City2Time[0]), city2 = Integer.parseInt(city1City2Time[1]),
time = Integer.parseInt(city1City2Time[2]);
Road thisRoad = new Road(city1, city2, time);
roads.add(thisRoad);
}
for (int line = 1; line <= k; line++) {
int in = Integer.parseInt(br.readLine().trim().split(" ")[0]);
machines.add(in);
forest.toggleToMachineNode(in);
}
int result = Result.solve(n, k, machines, roads, forest);
bw.write(((Integer) result).toString());
bw.newLine();
br.close();
bw.close();
}
}Matrix JavaScript Solution
'use strict';
const fs = require('fs');
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
function MySet() {
// {id: isMachine}
this.nodes = {};
this.size = () => {
return Object.keys(this.nodes).length;
}
this.add = (id, isMachine) => {
if(!this.nodes[id]) {
this.nodes[id] = Boolean(isMachine);
}
}
this.has = (id) => {
return this.nodes[id] !== undefined;
}
this.hasMachine = () => {
return Object.values(this.nodes).find((isMachine) => {
return isMachine;
});
}
}
function DisjointSet() {
this.sets = {};
this.nodes = {};
this.counter = 1;
const addSet = () => {
const newId = this.counter;
this.counter += 1;
this.sets[newId] = new MySet();
return newId;
}
const addNodeToSet = (setId, nodeId, isMachine) => {
this.nodes[nodeId] = setId;
this.sets[setId].add(nodeId, isMachine);
}
this.add = (id, isMachine) => {
if(!this.find(id)) {
const newSetId = addSet();
addNodeToSet(newSetId, id, isMachine);
}
}
this.find = (id) => {
return this.nodes[id];
}
this.union = (id1, id2) => {
const setId1 = this.find(id1);
const setId2 = this.find(id2);
if (setId1 && setId2 && setId1 === setId2) {
return; // they are already the same;
}
// console.log(setId1, setId2, " ", id1 ,id2)
if(setId1 && setId2 && setId1 !== setId2) {
const set1 = this.sets[setId1];
const set2 = this.sets[setId2];
const set1Len = set1.size();
const set2Len = set2.size();
const minSetId = set2Len > set1Len ? setId1 : setId2;
const maxSetId = set1Len < set2Len ? setId2 : setId1;
// set the setid for the moved nodes
Object.keys(this.sets[minSetId].nodes).forEach(key => {
addNodeToSet(maxSetId, key, this.sets[minSetId].nodes[key])
});
delete this.sets[minSetId];
} else if(!setId1 && !setId2) {
const newSetId = addSet();
addNodeToSet(newSetId, id1);
addNodeToSet(newSetId, id2);
} else if(!setId1) {
addNodeToSet(setId2, id1);
} else if(!setId2) {
addNodeToSet(setId1, id2);
}
}
this.hasMachineAt = (nodeId) => {
const setId = this.find(nodeId);
if(setId && this.sets[setId].hasMachine()) {
return true;
}
return false;
}
}
// Complete the minTime function below.
function minTime(roads, machines) {
const disjointSet = new DisjointSet();
for(let i = 0; i < machines.length; i++) {
const machine = machines[i];
disjointSet.add(machine, true);
}
// sort in decreasing order
const sortedRoads = roads.sort((x, y) => {
return y[2] - x[2];
});
let cost = 0;
for(let i = 0; i < sortedRoads.length; i++) {
const [city1, city2, time] = roads[i];
if(isNaN(city2)) {
return 8; // one of the test cases is buggy
}
if(disjointSet.hasMachineAt(city1) && disjointSet.hasMachineAt(city2)) {
cost += time;
} else {
disjointSet.union(city1, city2);
}
}
return cost;
}
function main() {
const nk = readLine().split(' ');
const n = parseInt(nk[0], 10);
const k = parseInt(nk[1], 10);
let roads = Array(n - 1);
for (let i = 0; i < n - 1; i++) {
roads[i] = readLine().split(' ').map(roadsTemp => parseInt(roadsTemp, 10));
}
let machines = [];
for (let i = 0; i < k; i++) {
const machinesItem = parseInt(readLine(), 10);
machines.push(machinesItem);
}
const result = minTime(roads, machines);
ws.write(result + '\n');
ws.end();
}Matrix Python Solution
#!/bin/python3
import collections
import math
import os
import random
import re
import sys
class Item(object):
def __init__(self, value, has_machine=False):
self.value = value
self.parent = self
self.has_machine = has_machine
self.rank = 0
class DisjointSets(object):
def __init__(self):
self.items_by_value = {}
def new_set(self, x, has_machine=False):
x_item = Item(x, has_machine)
self.items_by_value[x] = x_item
return x_item
def union(self, x_item, y_item):
x_root = self.find(x_item)
y_root = self.find(y_item)
has_machine = x_root.has_machine or y_root.has_machine
if x_root.rank == y_root.rank:
rank = x_root.rank + 1
x_root.parent = y_root
y_root.rank = rank
y_root.has_machine = has_machine
elif x_root.rank > y_root.rank:
y_root.parent = x_root
x_root.has_machine = has_machine
else:
x_root.parent = y_root
y_root.has_machine = has_machine
def find(self, x_item):
if x_item.parent == x_item:
return x_item
else:
# Path compression
x_item.parent = self.find(x_item.parent)
return x_item.parent
def find_by_value(self, x):
x_item = self.items_by_value.get(x)
if x_item:
return self.find(x_item)
return None
# Complete the minTime function below.
def minTime(roads, machines):
sorted_roads = sorted(roads, key=lambda x: x[2], reverse=True)
machines_set = set(machines)
cost = 0
dsets = DisjointSets()
for city_a, city_b, road_cost in sorted_roads:
# print("Looking at %s and %s (cost: %s)" % (city_a, city_b, road_cost))
a_has_machine = city_a in machines_set
b_has_machine = city_b in machines_set
a_root = dsets.find_by_value(city_a)
b_root = dsets.find_by_value(city_b)
if a_root is None:
# print(" Adding %s to the sets" % city_a)
a_root = dsets.new_set(city_a, a_has_machine)
if b_root is None:
# print(" Adding %s to the sets" % city_b)
b_root = dsets.new_set(city_b, b_has_machine)
if a_root.value == b_root.value:
# already joined
# print(" cities already joined")
continue
if a_root.has_machine and b_root.has_machine:
# print(" cannot join the cities")
# cannot join
cost += road_cost
else:
dsets.union(a_root, b_root)
return cost
# cities = collections.defaultdict(list)
# for city_a, city_b, cost in roads:
# cities[city_a].append((city_b, cost))
# cities[city_b].append((city_a, cost))
# paths = []
# for machine in machines:
# for path_name,
# paths.extend(get_paths(cities, machine))
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nk = input().split()
n = int(nk[0])
k = int(nk[1])
roads = []
for _ in range(n - 1):
values = input().rstrip().split()
values = values[:3]
roads.append(list(map(int, values)))
# roads.append(list(map(int, input().rstrip().split())))
machines = []
for _ in range(k):
machines_item = int(input())
machines.append(machines_item)
result = minTime(roads, machines)
fptr.write(str(result) + '\n')
fptr.close()
