Given positive integers N and M where N represents Vertices and M represents Edges. The power of each vertex is specified in an array arr[] and the connected vertex details are also specified in an array connected[]. When a vertex gets destroyed then all the connected vertex with less than or equal power gets destroyed (directly or indirectly). Find the minimum amount of power required to destroy all vertices.
Examples:
Input: N = 5, M = 2, arr[]={2, 3, 4, 5, 6}, connected[] = {{1, 5}, {3, 4}}
Output: 14Input: N = 4, M = 3, arr[] = {1, 2, 3, 4}, connected[] = {{1, 2}, {2, 3}, {3, 4}}
Output: 4
Approach: This can be solved with the following idea:
Consider the Example 1,
Example 1
In this example,
- 1 and 5 vertices are connected so if we power with 6 [2 ≤ 6 and 6 ≤ 6] we can destroy both vertices, power= 6
- Then 3 is not connected so we need to power with 3, power = 6+3 = 9
- Then 3 and 4 are connected so if we power with 5 [4 ≤ 5 and 5 ≤ 5] we can destroy both vertices, power = 6+3+5 = 14
So, a minimum of 14 amounts of power are required to destroy the whole garden.
- Here we can observe these connected vertices as a connected component and not connected vertices as a single graph component of the graph.
- We need to find the maximum power of each graph component using dfs algorithm then sum it up and return the sum.
Steps involved in the implementation of the code:
- Create an adjacency graph matrix[] and maintain a vector visited[].
- Iterate in all vertex and check whether it is visited or not.
- If not visited, start iterating from that vertex and get the maximum power value.
- Add it to the sum.
- Repeat this step until all vertices are visited.
- Return the sum.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>#include <iostream>using namespace std;set<int> vis;vector<vector<int> > graph;// Dfs traversalint dfs(int v, vector<int>& arr){ int val = arr[v - 1]; vis.insert(v); for (auto n : graph[v]) { if (!vis.count(n)) { // Find the maximum power in // each component val = max(val, dfs(n, arr)); } } // Return max value return val;}// Function to find power requiredlong long powerTheGarden(int n, int m, vector<int>& arr, vector<vector<int> >& connected){ long long ans = 0; graph.resize(n + 1); for (int i = 0; i <= n; i++) { graph[i] = vector<int>(); } // Build the undirected graph for (int i = 0; i < m; i++) { int x = connected[i][0]; int y = connected[i][1]; graph[x].push_back(y); graph[y].push_back(x); } vis.clear(); for (int i = 1; i <= n; i++) { if (!vis.count(i)) { vis.insert(i); // Sum of all power of the // connected vertices ans += dfs(i, arr); } } // Return the sum return ans;}// Driver codeint main(){ int N = 5, M = 2; vector<int> arr = { 2, 3, 4, 5, 6 }; vector<vector<int> > connected = { { 1, 5 }, { 3, 4 } }; // Function call cout << powerTheGarden(N, M, arr, connected); return 0;} |
Java
import java.util.*;public class Main { static Set<Integer> vis = new HashSet<>(); static List<List<Integer> > graph = new ArrayList<>(); // dfs traversal public static int dfs(int v, List<Integer> arr) { int val = arr.get(v - 1); vis.add(v); for (int n : graph.get(v)) { if (!vis.contains(n)) { // find the maximum poison in each component val = Math.max(val, dfs(n, arr)); } } // return max value return val; } public static long poisonTheGarden(int n, int m, List<Integer> arr, List<List<Integer> > connected) { long ans = 0; graph = new ArrayList<>(n + 1); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } // build the undirected graph for (int i = 0; i < m; i++) { int x = connected.get(i).get(0); int y = connected.get(i).get(1); graph.get(x).add(y); graph.get(y).add(x); } vis.clear(); for (int i = 1; i <= n; i++) { if (!vis.contains(i)) { vis.add(i); // sum of all poison of the connected plants ans += dfs(i, arr); } } // return the sum return ans; } public static void main(String[] args) { int N = 5, M = 2; List<Integer> arr = Arrays.asList(2, 3, 4, 5, 6); List<List<Integer> > connected = Arrays.asList( Arrays.asList(1, 5), Arrays.asList(3, 4)); System.out.println( poisonTheGarden(N, M, arr, connected)); }} |
Python
from collections import defaultdictimport syssys.setrecursionlimit(10**6)vis = set()graph = defaultdict(list)# dfs traversaldef dfs(v, arr): val = arr[v - 1] vis.add(v) for n in graph[v]: if n not in vis: # find the maximum poison in each component val = max(val, dfs(n, arr)) # return max value return valdef poisonTheGarden(n, m, arr, connected): ans = 0 # build the undirected graph for i in range(m): x = connected[i][0] y = connected[i][1] graph[x].append(y) graph[y].append(x) vis.clear() for i in range(1, n + 1): if i not in vis: vis.add(i) # sum of all poison of the connected plants ans += dfs(i, arr) # return the sum return ansN = 5M = 2arr = [2, 3, 4, 5, 6]connected = [[1, 5], [3, 4]]print(poisonTheGarden(N, M, arr, connected)) |
C#
// C# code for the above approach:using System;using System.Collections.Generic;class Program{ static HashSet<int> vis; static List<List<int>> graph; // dfs traversal static int Dfs(int v, List<int> arr) { // find the maximum poison in each component int val = arr[v - 1]; vis.Add(v); foreach (int n in graph[v]) { if (!vis.Contains(n)) { val = Math.Max(val, Dfs(n, arr)); } } // return max value return val; } static long PowerTheGarden(int n, int m, List<int> arr, List<List<int>> connected) { long ans = 0; graph = new List<List<int>>(); for (int i = 0; i <= n; i++) { graph.Add(new List<int>()); } // build the undirected graph for (int i = 0; i < m; i++) { int x = connected[i][0]; int y = connected[i][1]; graph[x].Add(y); graph[y].Add(x); } vis = new HashSet<int>(); for (int i = 1; i <= n; i++) { if (!vis.Contains(i)) { vis.Add(i); // sum of all poison of the connected plants ans += Dfs(i, arr); } } // return the sum return ans; } static void Main(string[] args) { int N = 5, M = 2; List<int> arr = new List<int> { 2, 3, 4, 5, 6 }; List<List<int>> connected = new List<List<int>> { new List<int> { 1, 5 }, new List<int> { 3, 4 } }; Console.WriteLine(PowerTheGarden(N, M, arr, connected)); }} |
Javascript
const Set = require('collections/set');let vis = new Set();let graph = [];function dfs(v, arr) { let val = arr[v - 1]; vis.add(v); for (let n of graph[v]) { if (!vis.has(n)) { val = Math.max(val, dfs(n, arr)); } } return val;}function poisonTheGarden(n, m, arr, connected) { let ans = 0; graph = new Array(n + 1); for (let i = 0; i <= n; i++) { graph[i] = []; } for (let i = 0; i < m; i++) { let x = connected[i][0]; let y = connected[i][1]; graph[x].push(y); graph[y].push(x); } vis.clear(); for (let i = 1; i <= n; i++) { if (!vis.has(i)) { vis.add(i); ans += dfs(i, arr); } } return ans;}let N = 5, M = 2;let arr = [2, 3, 4, 5, 6];let connected = [[1, 5], [3, 4]];console.log(poisonTheGarden(N, M, arr, connected)); |
Output
14
Time Complexity: O(N)
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
