Commutable Islands














































Commutable Islands



There are A islands and there are M bridges connecting them. Each bridge has some cost attached to it.

We need to find bridges with minimal cost such that all islands are connected.

It is guaranteed that input data will contain at least one possible scenario in which all islands are connected with each other.

Input Format:

The first argument contains an integer, A, representing the number of islands.
The second argument contains an 2-d integer matrix, B, of size M x 3:
    => Island B[i][0] and B[i][1] are connected using a bridge of cost B[i][2].

Output Format:

Return an integer representing the minimal cost required.

Constraints:

1 <= A, M <= 6e4
1 <= B[i][0], B[i][1] <= A
1 <= B[i][2] <= 1e3

Examples:

Input 1:
    A = 4
    B = [   [1, 2, 1]
            [2, 3, 4]
            [1, 4, 3]
            [4, 3, 2]
            [1, 3, 10]  ]

Output 1:
    6

Explanation 1:
    We can choose bridges (1, 2, 1), (1, 4, 3) and (4, 3, 2), where the total cost incurred will be (1 + 3 + 2) = 6.

Input 2:
    A = 4
    B = [   [1, 2, 1]
            [2, 3, 2]
            [3, 4, 4]
            [1, 4, 3]   ]

Output 2:
    6

Explanation 2:
    We can choose bridges (1, 2, 1), (2, 3, 2) and (1, 4, 3), where the total cost incurred will be (1 + 2 + 3) = 6.
#include <bits/stdc++.h>
using namespace std;

vector<int >par;
int parent(int x){
while(x!=par[x]){
x=par[x];
}
return x;
}
void uni(int a,int b){
int p1=parent(a),p2=parent(b);
par[p1]=p2;
}

int kruskal(pair<int, pair<int, int> > p[],int edges)
{
int x, y;
int cost, minimumCost = 0;
for(int i = 0;i < edges;++i)
{
x = p[i].second.first;
y = p[i].second.second;
cost = p[i].first;
if(parent(x) != parent(y))
{
minimumCost += cost;
uni(x, y);
}
}
return minimumCost;
}

int solve(int A, vector<vector<int> > &B) {
pair<int, pair<int, int> > p[B.size()];
int maxi=0;
for(int i=0;i<B.size();i++){
p[i] = make_pair(B[i][2], make_pair(B[i][0], B[i][1]));
maxi=max(maxi,max(B[i][0],B[i][1]));
}
vector<int>tmp(A+1,0);
for(int i=0;i<=A;i++)tmp[i]=i;
par=tmp;
sort(p,p+B.size());
return kruskal(p,B.size());
}

int main() {
vector<vector<int> >v={{1, 2, 1},{2, 3, 2},{3, 4, 4},{1, 4, 3}};
int z=solve(4,v);
cout<<z<<endl;
}


More Articles of Khitish Panigrahi:

Name Views Likes
Rotate Image 142 0
Edit Distance 88 1
Integer to Roman 117 2
Roman to Integer 107 2
Shortest Path Problem 111 2
Dijkstra 115 2
Hamiltonian Path 105 3
Travelling Salesman Problem 109 3
Hamiltonian Cycle 108 3
Number of Operations to Make Network Connected 104 2
Time Needed to Inform All Employees 101 2
Last Stone Weight II(any weight can be picked) 113 2
Last Stone Weight 119 2
Course Schedule II (print the order) 91 2
Course Schedule 103 2
0-1knapsack 116 2
Commutable Islands 224 2
Cheapest Flights Within K Stops 114 2
Friend Circles 99 2
Longest Palindromic Subsequence (Print Subsequence) 107 2
Longest Palindromic Subsequence (print only length) 98 2
longest palindromic substring(improved) 95 2
Longest Common Subsequence (Print the Subsequence) 98 2
Longest Common Subsequence (Print only Length) 100 2
Cycle in Undirected Graph 122 2
IOT SMART HOME 142 2
Working of Home Networks 100 2
Smart and Safe Cab Finder Algorithm 146 2
Minimum Falling Path Sum 174 3
Maximum Length of a Concatenated String with Unique Characters 100 3
Stack Pushing Game(Push Dominoes Game) 101 3
Boats to Save People 120 3
Find Single Non-repeated Number 96 3
Create Ranges 90 3
Triangle 95 3
Restore IP Addresses 100 4
Number of Matching Subsequences 89 3
Max Area of Island 101 3
Number of Islands 85 3
Is Subsequence 99 3
Word Break 98 3
Perfect Number 97 3
Longest Arithmetic Sequence 95 3
Container With Most Water 101 3
Maximal Square 95 3
Best Time to Buy and Sell Stock 100 3
Distance Between Bus Stops 97 3
Validate IP Address 110 3
Longest Mountain in Array 105 4
Sequential Digits 101 3
Path with Maximum Gold 112 3
House Robber with houses arranged in circular manner 127 3
Increasing Triplet Subsequence 110 5
4Sum 106 3
3Sum 97 3
ZigZag Conversion 133 4
House Robber 97 3
Minimum Path Sum 98 3
Unique Paths with obstacles 90 2
Find and Replace Pattern 100 3
Minimum Size Subarray Sum 96 3
Maximum Subarray 103 5
Find All Anagrams in a String 65 3
Permutation in String 66 3
Subarray Sum Equals K 102 3
Maximum Product Subarray 81 4
Permutation with duplicates 77 6
Subsets with duplicates 77 7
Partition Equal Subset Sum 69 5
Relative Sort Array 65 3
Permutations 67 4
Combination Sum 125 4
All combinations that add up to a given sum 69 3
Combinations 84 7
Palindrome Partitioning 70 3
Climbing Stairs 86 5
Fibonacci Number 83 5
Unique Paths 76 3
Longest Increasing Subsequence 66 8
Gas Station 75 7
Minimum number of Perfect square needed to form a number 60 7
Permutation Sequence 141 16
Coin Change 71 6
Multiple Word Searching Algorithm 78 8
Word Search 67 6
Valid Anagram 91 8
Remove Nth Node From End of List 90 6
Linked List Cycle 67 6
Implement strStr() 67 4
Odd Even Linked List 60 6
Valid Palindrome 64 4
Maximum Depth of Binary Tree 60 3
Binary Tree Zigzag Level Order Traversal 78 4
Kth Smallest Element in a BST 47 2
Evaluate Reverse Polish Notation 64 3
String to Integer (atoi) 82 4
Intersection of Two Linked Lists 69 3
Multiply Strings 70 5
Palindromic Substrings 59 4
Add Strings 56 2
Longest Substring Without Repeating Characters 63 4
Longest Palindromic Substring 62 2
Jump Game 68 3
Majority Element 59 2
Top K Frequent Elements 91 7
Factorial Trailing Zeroes 53 2
Excel Sheet Column Number 55 3
Find Peak Element 84 4
Merge Intervals 57 3
Letter Combinations of a Phone Number 69 4
Populating Next Right Pointers in Each Node 66 2
Invert Binary Tree 62 4
Swap Nodes in Pairs 60 5
3Sum Closest 56 2
Permutation Sequence 85 4
Letter Tile Possibilities 124 3
The k-th Lexicographical String of All Happy Strings of Length n 70 3
Children Sum Parent 129 5
Check if Binary Tree is BST 126 5
Delete Node in Linked List without a head pointer 96 2
Connect all siblings in a Binary Search Tree 86 2
Delete a node from BST in C++ 96 3

Comments