Maximum money that can be collected among friends based on given conditions
Given an array arr[](1-based indexing) consisting of N positive integers such that arr[i] denotes the amount of the ith person. Also given are two 2D arrays say friends[][2] and groups[][2] such that each pair friends[i][0] and friends[i][1] are friends and form groups. Each pair groups[i][0] and groups[i][0] denotes the friends containing groups[i][0] and groups[i][1] can be friends among themselves.
The task is to find the maximum money that can be collected amongst themselves on the basis of the following conditions:
- If A and B are friends and B and C are friends then A and C are friends.
- If there can be a friendship between a group of people having A and a group of people having B and if there can be a friendship between a group of B and a group of C then there is a friendship between a group of A and a group of C.
- A set of friends forms the groups.
Examples:
Input: arr[] = {5, 2, 3, 6, 1, 9, 8}, friends[][] = {{1, 2}, {2, 3}, {4, 5}, {6, 7}}, groups[][] = {{1, 4}, {1, 6}}
Output: 27
Explanation:
Total Cost in Group 1 = 5 + 2 + 3 = 10.
Total Cost in Group 2 = 6 + 1 = 7.
Total Cost in Group 3 = 9 + 8 = 17.
As the group 1 can borrow money among both the group 2 and group 3. Therefore, the maximum money collected is 10 + 17 = 27.Input: arr[] = {1, 2, 3, 4, 5, 6, 7}, friends[][] = {{1, 2}, {2, 3}, {4, 5}, {6, 7}}, groups[][] = {{1, 4}, {1, 6}}
Output: 19
Approach: The given problem can be solved by forming a group of friends and find the amount of money each group can have. The idea is to use Disjoint Set Union by making one of the group members a parent. Follow the below steps to solve the problem:
- While forming the group add the amount of each group of friends and store this amount with the parent of this group.
- Add an edge between different groups where two vertices of an edge show that these two groups can be friends of each other.
- Add an edge between the parent members of the group.
- Since, the parent stores the amount of money the corresponding group has, then the problem is reduced to find the maximum sum path from the node to the leaf where each node in the path represents the amount of money the group has.
- After completing the above steps, print the value of the maximum amount that can be collected.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define N 100001int n;int amt[N];long long dp[N], c[N];int parent[N];long long sz[N];vector<int> v[N];// Function to find the parent of each// node in the graphint find(int i){ // If the parent is the same node // itself if (parent[i] == i) return i; // Recursively find the parent return parent[i] = find(parent[i]);}// Function to merge the friends of// each groupsvoid Union(int a, int b){ // Find the parents of a and b int p1 = find(a); int p2 = find(b); // If the parents are the same // then return if (p1 == p2) return; // If the size of the parent p1 // is less than the p2, then // swap the parents p1 and p2 if (sz[p1] < sz[p2]) { swap(p1, p2); } parent[p2] = p1; sz[p1] += sz[p2]; // Money in the group of p2 is // added to the p1 and p2 is // now the member of p1 c[p1] += c[p2]; // p2 is now the member of p1 c[p2] = 0;}// Function to calculate the maximum// amount collected among friendsvoid dfs(int src, int par){ dp[src] = c[src]; long long mx = 0; // Traverse the adjacency list // of the src node for (auto x : v[src]) { if (x == par) continue; dfs(x, src); // Calculate the maximum // amount of the group mx = max(mx, dp[x]); } // Adding the max amount of money // with the current group dp[src] += mx;}// Function to find the maximum money// collected among friendsvoid maximumMoney( int n, int amt[], vector<pair<int, int> > friends, vector<pair<int, int> > groups){ // Iterate over the range [1, N] for (int i = 1; i <= n; i++) { // Initialize the parent and // the size of each node i parent[i] = i; sz[i] = 1; c[i] = amt[i - 1]; } int p = friends.size(); // Merging friends into groups for (int i = 0; i < p; ++i) { // Perform the union operation Union(friends[i].first, friends[i].second); } int m = groups.size(); // Finding the parent of group // in which member is present for (int i = 0; i < m; ++i) { // Find the parent p1 and p2 int p1 = find(groups[i].first); int p2 = find(groups[i].second); // p1 and p2 are not in same // group then add an edge if (p1 != p2) { // These two groups can be // made friends. Hence, // adding an edge v[p1].push_back(p2); v[p2].push_back(p1); } } // Starting dfs from node which // is the parent of group in // which 1 is present dfs(find(1), 0); long long ans = 0; // Ans is the maximum money // collected by each group for (int i = 1; i <= n; i++) { ans = max(ans, dp[find(i)]); } // Print the answer cout << ans << endl;}// Driver Codesigned main(){ int amt[] = { 5, 2, 3, 6, 1, 9, 8 }; n = sizeof(amt) / sizeof(amt[0]); vector<pair<int, int> > friends = { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 6, 7 } }; vector<pair<int, int> > groups = { { 1, 4 }, { 1, 6 } }; maximumMoney(n, amt, friends, groups); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { static int N = 100001; static int[] amt = new int[N]; static int[] dp = new int[N]; static int[] c = new int[N]; static int[] parent = new int[N]; static int[] sz = new int[N]; static ArrayList<Integer>[] v = new ArrayList[N]; // Function to find the parent of each // node in the graph static int find(int i) { // If the parent is the same node // itself if (parent[i] == i) return i; parent[i] = find(parent[i]); // Recursively find the parent return parent[i]; } // Function to merge the friends of // each groups static void Union(int a, int b) { // Find the parents of a and b int p1 = find(a); int p2 = find(b); // If the parents are the same // then return if (p1 == p2) return; // If the size of the parent p1 // is less than the p2, then // swap the parents p1 and p2 if (sz[p1] < sz[p2]) { int temp = p1; p1 = p2; p2 = temp; } parent[p2] = p1; sz[p1] += sz[p2]; // Money in the group of p2 is // added to the p1 and p2 is // now the member of p1 c[p1] += c[p2]; // p2 is now the member of p1 c[p2] = 0; } // Function to calculate the maximum // amount collected among friends static void dfs(int src, int par) { dp[src] = c[src]; int mx = 0; // Traverse the adjacency list // of the src node for (int x : v[src]) { if (x == par) continue; dfs(x, src); // Calculate the maximum // amount of the group mx = Math.max(mx, dp[x]); } // Adding the max amount of money // with the current group dp[src] += mx; } // Function to find the maximum money // collected among friends static void maximumMoney(int n, int[] amt, int[][] friends, int[][] groups) { // Iterate over the range [1, N] for (int i = 1; i <= n; i++) { // Initialize the parent and // the size of each node i parent[i] = i; sz[i] = 1; c[i] = amt[i - 1]; v[i] = new ArrayList<>(); } int p = friends.length; // Merging friends into groups for (int i = 0; i < p; i++) // Perform the union operation Union(friends[i][0], friends[i][1]); int m = groups.length; // Finding the parent of group // in which member is present for (int i = 0; i < m; i++) { // Find the parent p1 and p2 int p1 = find(groups[i][0]); int p2 = find(groups[i][1]); // p1 and p2 are not in same // group then add an edge if (p1 != p2) { // These two groups can be // made friends. Hence, // adding an edge v[p1].add(p2); v[p2].add(p1); } } // Starting dfs from node which // is the parent of group in // which 1 is present dfs(find(1), 0); int ans = 0; // Ans is the maximum money // collected by each group for (int i = 1; i <= n; i++) ans = Math.max(ans, dp[find(i)]); // Print the answer System.out.println(ans); } // Driver Function public static void main(String[] args) throws java.lang.Exception { // Inputs int n = 7; int[] amt = { 5, 2, 3, 6, 1, 9, 8 }; int[][] friends = { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 6, 7 } }; int[][] groups = { { 1, 4 }, { 1, 6 } }; // Function call maximumMoney(n, amt, friends, groups); }} |
Python3
# Python3 program for the above approachN = 100001amt = [0] * Ndp = [0] * Nc = [0] * Nparent = [0] * Nsz = [0] * Nv = [[] for i in range(N)]# Function to find the parent of each# node in the graphdef find(i): # If the parent is the same node # itself if (parent[i] == i): return i parent[i] = find(parent[i]) return parent[i]# Function to merge the friends of# each groupsdef Union(a, b): # Find the parents of a and b p1 = find(a) p2 = find(b) # If the parents are the same # then return if (p1 == p2): return # If the size of the parent p1 # is less than the p2, then # swap the parents p1 and p2 if (sz[p1] < sz[p2]): temp = p1 p1 = p2 p2 = temp parent[p2] = p1 sz[p1] += sz[p2] # Money in the group of p2 is # added to the p1 and p2 is # now the member of p1 c[p1] += c[p2] # p2 is now the member of p1 c[p2] = 0# Function to calculate the maximum# amount collected among friendsdef dfs(src, par): dp[src] = c[src] mx = 0 # Traverse the adjacency list # of the src node for x in v[src]: if (x == par): continue dfs(x, src) # Calculate the maximum # amount of the group mx = max(mx, dp[x]) # Adding the max amount of money # with the current group dp[src] += mx# Function to find the maximum money# collected among friendsdef maximumMoney(n, amt, friends, groups): # Iterate over the range [1, N] for i in range(1, n + 1): # Initialize the parent and # the size of each node i parent[i] = i sz[i] = 1 c[i] = amt[i - 1] p = len(friends) # Merging friends into groups for i in range(p): # Perform the union operation Union(friends[i][0], friends[i][1]) m = len(groups) # Finding the parent of group # in which member is present for i in range(m): # Find the parent p1 and p2 p1 = find(groups[i][0]) p2 = find(groups[i][1]) # p1 and p2 are not in same # group then add an edge if (p1 != p2): # These two groups can be # made friends. Hence, # adding an edge v[p1].append(p2) v[p2].append(p1) # Starting dfs from node which # is the parent of group in # which 1 is present dfs(find(1), 0) ans = 0 # Ans is the maximum money # collected by each group for i in range(1, n + 1): ans = max(ans, dp[find(i)]) # Print the answer print(ans)# Driver Codeamt = [ 5, 2, 3, 6, 1, 9, 8 ]n = len(amt)friends = [ [ 1, 2 ], [ 2, 3 ], [ 4, 5 ], [ 6, 7 ] ]groups = [ [ 1, 4 ], [ 1, 6 ] ]maximumMoney(n, amt, friends, groups)# This code is contributed by _saurabh_jaiswal |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;using System.Linq;class GFG { static int N = 100001; static int[] amt = new int[N]; static int[] dp = new int[N]; static int[] c = new int[N]; static int[] parent = new int[N]; static int[] sz = new int[N]; static List<int>[] v = new List<int>[ N ]; // Function to find the parent of each // node in the graph static int Find(int i) { // If the parent is the same node // itself if (parent[i] == i) return i; parent[i] = Find(parent[i]); // Recursively find the parent return parent[i]; } // Function to merge the friends of // each groups static void Union(int a, int b) { // Find the parents of a and b int p1 = Find(a); int p2 = Find(b); // If the parents are the same // then return if (p1 == p2) return; // If the size of the parent p1 // is less than the p2, then // swap the parents p1 and p2 if (sz[p1] < sz[p2]) { int temp = p1; p1 = p2; p2 = temp; } parent[p2] = p1; sz[p1] += sz[p2]; // Money in the group of p2 is // added to the p1 and p2 is // now the member of p1 c[p1] += c[p2]; // p2 is now the member of p1 c[p2] = 0; } // Function to calculate the maximum // amount collected among friends static void Dfs(int src, int par) { dp[src] = c[src]; int mx = 0; // Traverse the adjacency list // of the src node foreach(int x in v[src]) { if (x == par) continue; Dfs(x, src); // Calculate the maximum // amount of the group mx = Math.Max(mx, dp[x]); } // Adding the max amount of money // with the current group dp[src] += mx; } // Function to find the maximum money // collected among friends static void MaximumMoney(int n, int[] amt, int[][] friends, int[][] groups) { // Iterate over the range [1, N] for (int i = 1; i <= n; i++) { // Initialize the parent and // the size of each node i parent[i] = i; sz[i] = 1; c[i] = amt[i - 1]; v[i] = new List<int>(); } int p = friends.Length; // Merging friends into groups for (int i = 0; i < p; i++) // Perform the union operation Union(friends[i][0], friends[i][1]); int m = groups.Length; // Finding the parent of group // in which member is present for (int i = 0; i < m; i++) { // Find the parent p1 and p2 int p1 = Find(groups[i][0]); int p2 = Find(groups[i][1]); // p1 and p2 are not in same // group then add an edge if (p1 != p2) { // These two groups can be // made friends. Hence, // adding an edge v[p1].Add(p2); v[p2].Add(p1); } } // Starting dfs from node which // is the parent of group in // which 1 is present Dfs(Find(1), 0); int ans = 0; // Ans is the maximum money // collected by each group for (int i = 1; i <= n; i++) ans = Math.Max(ans, dp[Find(i)]); // Print the answer Console.WriteLine(ans); } // Driver Function static void Main(string[] args) { // Inputs int n = 7; int[] amt = { 5, 2, 3, 6, 1, 9, 8 }; int[][] friends = { new int[] { 1, 2 }, new int[] { 2, 3 }, new int[] { 4, 5 }, new int[] { 6, 7 } }; int[][] groups = { new int[] { 1, 4 }, new int[] { 1, 6 } }; // Function call MaximumMoney(n, amt, friends, groups); }}// This code is contributed by Prajwal Kandekar |
Javascript
<script>// JavaScript program for the above approachlet N = 100001let n;let amt = new Array(N);let dp = new Array(N), c = new Array(N);let parent = new Array(N);let sz = new Array(N);let v = new Array(N).fill(0).map(() => []);// Function to find the parent of each// node in the graphfunction find(i) { // If the parent is the same node // itself if (parent[i] == i) return i; // Recursively find the parent return parent[i] = find(parent[i]);}// Function to merge the friends of// each groupsfunction Union(a, b) { // Find the parents of a and b let p1 = find(a); let p2 = find(b); // If the parents are the same // then return if (p1 == p2) return; // If the size of the parent p1 // is less than the p2, then // swap the parents p1 and p2 if (sz[p1] < sz[p2]) { let temp = p1; p1 = p2; p2 = temp; } parent[p2] = p1; sz[p1] += sz[p2]; // Money in the group of p2 is // added to the p1 and p2 is // now the member of p1 c[p1] += c[p2]; // p2 is now the member of p1 c[p2] = 0;}// Function to calculate the maximum// amount collected among friendsfunction dfs(src, par) { dp[src] = c[src]; let mx = 0; // Traverse the adjacency list // of the src node for (let x of v[src]) { if (x == par) continue; dfs(x, src); // Calculate the maximum // amount of the group mx = Math.max(mx, dp[x]); } // Adding the max amount of money // with the current group dp[src] += mx;}// Function to find the maximum money// collected among friendsfunction maximumMoney(n, amt, friends, groups) { // Iterate over the range [1, N] for (let i = 1; i <= n; i++) { // Initialize the parent and // the size of each node i parent[i] = i; sz[i] = 1; c[i] = amt[i - 1]; } let p = friends.length; // Merging friends into groups for (let i = 0; i < p; ++i) { // Perform the union operation Union(friends[i][0], friends[i][1]); } let m = groups.length; // Finding the parent of group // in which member is present for (let i = 0; i < m; ++i) { // Find the parent p1 and p2 let p1 = find(groups[i][0]); let p2 = find(groups[i][1]); // p1 and p2 are not in same // group then add an edge if (p1 != p2) { // These two groups can be // made friends. Hence, // adding an edge v[p1].push(p2); v[p2].push(p1); } } // Starting dfs from node which // is the parent of group in // which 1 is present dfs(find(1), 0); let ans = 0; // Ans is the maximum money // collected by each group for (let i = 1; i <= n; i++) { ans = Math.max(ans, dp[find(i)]); } // Print the answer document.write(ans + "<br>");}// Driver Codeamt = [5, 2, 3, 6, 1, 9, 8];n = amt.length;let friends = [[1, 2], [2, 3], [4, 5], [6, 7]];let groups = [[1, 4], [1, 6]];maximumMoney(n, amt, friends, groups);</script> |
Output
27
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
