Given a graph with N nodes having values either P or M. Also given K pairs of integers as (x, y) representing the edges in the graph such that if a is connected to b and b is connected to c then a and c will also be connected.
A single connected component is called a group. The group can have both P and M values. If the P values are more than the M values this group is called P influenced and similarly for M. If the number of P’s and M’s are equal then it is called a neutral group. The task is to find the number of P influenced, M influenced and, Neutral groups.
Examples:
Input: Nodes[] = {P, M, P, M, P}, edges[][] = {
{1, 3},
{4, 5},
{3, 5}}
Output:
P = 1
M = 1
N = 0
There will be two groups of indexes
{1, 3, 4, 5} and {2}.
The first group is P influenced and
the second one is M influenced.Input: Nodes[] = {P, M, P, M, P}, edges[][] = {
{1, 3},
{4, 5}}
Output:
P = 1
M = 2
N = 0
Approach: It is easier to construct a graph with adjacency list and loop from 1 to N and do DFS and check the count of P and M.
Another way is to use DSU with a little modification that size array will be of pair so that it can maintain the count of both M and P. In this approach, there is no need to construct the graph as the merge operation will take care of the connected component. Note that you should have the knowledge of DSU by size/rank for optimization.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// To store the parents// of the current nodevector<int> par;// To store the size of M and Pvector<pair<int, int> > sz;// Function for initializationvoid init(vector<char>& nodes){ // Size of the graph int n = (int)nodes.size(); par.clear(); sz.clear(); par.resize(n + 1); sz.resize(n + 1); for (int i = 0; i <= n; ++i) { par[i] = i; if (i > 0) { // If the node is P if (nodes[i - 1] == 'P') sz[i] = { 0, 1 }; // If the node is M else sz[i] = { 1, 0 }; } }}// To find the parent of// the current nodeint parent(int i){ while (par[i] != i) i = par[i]; return i;}// Merge functionvoid union(int a, int b){ a = parent(a); b = parent(b); if (a == b) return; // Total size by adding number of M and P int sz_a = sz[a].first + sz[a].second; int sz_b = sz[b].first + sz[b].second; if (sz_a < sz_b) swap(a, b); par[b] = a; sz[a].first += sz[b].first; sz[a].second += sz[b].second; return;}// Function to calculate the influenced valuevoid influenced(vector<char>& nodes, vector<pair<int, int> > connect){ // Number of nodes int n = (int)nodes.size(); // Initialization function init(nodes); // Size of the connected vector int k = connect.size(); // Performing union operation for (int i = 0; i < k; ++i) { union(connect[i].first, connect[i].second); } // ne = Number of neutal groups // ma = Number of M influenced groups // pe = Number of P influenced groups int ne = 0, ma = 0, pe = 0; for (int i = 1; i <= n; ++i) { int x = parent(i); if (x == i) { if (sz[i].first == sz[i].second) { ne++; } else if (sz[i].first > sz[i].second) { ma++; } else { pe++; } } } cout << "P = " << pe << "\nM = " << ma << "\nN = " << ne << "\n";}// Driver codeint main(){ // Nodes at each index ( 1 - base indexing ) vector<char> nodes = { 'P', 'M', 'P', 'M', 'P' }; // Connected Pairs vector<pair<int, int> > connect = { { 1, 3 }, { 3, 5 }, { 4, 5 } }; influenced(nodes, connect); return 0;} |
Java
// Java implementation of the approach import java.io.*;import java.util.*;class GFG{ // To store the parents // of the current node static ArrayList<Integer> par = new ArrayList<Integer>();// To store the size of M and P static ArrayList< ArrayList<Integer>> sz = new ArrayList< ArrayList<Integer>>(); // Function for initialization static void init(ArrayList<Character> nodes){ // Size of the graph int n = nodes.size(); for(int i = 0; i <= n; ++i) { par.add(i); if (i == 0) { sz.add(new ArrayList<Integer>( Arrays.asList(0, 0))); } if (i > 0) { // If the node is P if (nodes.get(i - 1) == 'P') { sz.add(new ArrayList<Integer>( Arrays.asList(0, 1))); } // If the node is M else { sz.add(new ArrayList<Integer>( Arrays.asList(1, 0))); } } }}// To find the parent of // the current node static int parent(int i) { while (par.get(i) != i) { i = par.get(i); } return i;}// Merge function static void union(int a, int b){ a = parent(a); b = parent(b); if (a == b) { return; } // Total size by adding number // of M and P int sz_a = sz.get(a).get(0) + sz.get(a).get(1); int sz_b = sz.get(b).get(0) + sz.get(b).get(1); if (sz_a < sz_b) { int temp = a; a = b; b = temp; } par.set(b, a); sz.get(a).set(0, sz.get(a).get(0) + sz.get(b).get(0)); sz.get(a).set(1, sz.get(a).get(1) + sz.get(b).get(1)); return;}// Function to calculate the influenced value static void influenced(ArrayList<Character> nodes, ArrayList<ArrayList<Integer>> connect){ // Number of nodes int n = nodes.size(); // Initialization function init(nodes); // Size of the connected vector int k = connect.size(); // Performing union operation for(int i = 0; i < k; ++i) { union(connect.get(i).get(0), connect.get(i).get(1)); } // ne = Number of neutal groups // ma = Number of M influenced groups // pe = Number of P influenced groups int ne = 0, ma = 0, pe = 0; for(int i = 1; i <= n; ++i) { int x = parent(i); if (x == i) { if (sz.get(i).get(0) == sz.get(i).get(1)) { ne++; } else if (sz.get(i).get(0) > sz.get(i).get(1)) { ma++; } else { pe++; } } } System.out.println("P = " + pe + "\nM = " + ma + "\nN = " + ne);}// Driver codepublic static void main(String[] args) { // Nodes at each index ( 1 - base indexing ) ArrayList<Character> nodes = new ArrayList<Character>(); nodes.add('P'); nodes.add('M'); nodes.add('P'); nodes.add('M'); nodes.add('P'); // Connected Pairs ArrayList< ArrayList<Integer>> connect = new ArrayList< ArrayList<Integer>>(); connect.add(new ArrayList<Integer>( Arrays.asList(1, 3))); connect.add(new ArrayList<Integer>( Arrays.asList(3, 5))); connect.add(new ArrayList<Integer>( Arrays.asList(4, 5))); influenced(nodes, connect); }}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 implementation of the approach# To store the parents# of the current nodepar = []# To store the size of M and Psz = []# Function for initializationdef init(nodes): # Size of the graph n = len(nodes) for i in range(n + 1): par.append(0) sz.append(0) for i in range(n + 1): par[i] = i if (i > 0): # If the node is P if (nodes[i - 1] == 'P'): sz[i] = [0, 1] # If the node is M else: sz[i] = [1, 0]# To find the parent of# the current nodedef parent(i): while (par[i] != i): i = par[i] return i# Merge functiondef union(a, b): a = parent(a) b = parent(b) if (a == b): return # Total size by adding number of M and P sz_a = sz[a][0] + sz[a][1] sz_b = sz[b][0] + sz[b][1] if (sz_a < sz_b): a, b = b, a par[b] = a sz[a][0] += sz[b][0] sz[a][1] += sz[b][1] return# Function to calculate the influenced valuedef influenced(nodes,connect): # Number of nodes n = len(nodes) # Initialization function init(nodes) # Size of the connected vector k = len(connect) # Performing union operation for i in range(k): union(connect[i][0], connect[i][1]) # ne = Number of neutal groups # ma = Number of M influenced groups # pe = Number of P influenced groups ne = 0 ma = 0 pe = 0 for i in range(1, n + 1): x = parent(i) if (x == i): if (sz[i][0] == sz[i][1]): ne += 1 elif (sz[i][0] > sz[i][1]): ma += 1 else: pe += 1 print("P =",pe,"\nM =",ma,"\nN =",ne)# Driver code# Nodes at each index ( 1 - base indexing )nodes = [ 'P', 'M', 'P', 'M', 'P' ]# Connected Pairsconnect = [ [ 1, 3 ], [ 3, 5 ], [ 4, 5 ] ]influenced(nodes, connect)# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System;using System.Collections.Generic;class GFG{ // To store the parents // of the current nodestatic List<int> par = new List<int>();// To store the size of M and P static List<List<int>> sz = new List<List<int>>();// Function for initializationstatic void init(List<char> nodes){ // Size of the graph int n = nodes.Count; for(int i = 0; i <= n; ++i) { par.Add(i); if (i == 0) { sz.Add(new List<int>(){0, 0}); } if (i > 0) { // If the node is P if (nodes[i - 1] == 'P') { sz.Add(new List<int>(){0, 1}); } // If the node is M else { sz.Add(new List<int>(){1, 0}); } } }}// To find the parent of // the current node static int parent(int i) { while (par[i] != i) { i = par[i]; } return i;}// Merge functionstatic void union(int a, int b){ a = parent(a); b = parent(b); if (a == b) { return; } // Total size by adding number // of M and P int sz_a = sz[a][0] + sz[a][1]; int sz_b = sz[b][0] + sz[b][1]; if (sz_a < sz_b) { int temp = a; a = b; b = temp; } par[b] = a; sz[a][0] += sz[b][0]; sz[a][1] += sz[b][1]; return;}// Function to calculate the influenced value static void influenced(List<char> nodes, List<List<int>> connect){ // Number of nodes int n = nodes.Count; // Initialization function init(nodes); // Size of the connected vector int k = connect.Count; // Performing union operation for(int i = 0; i < k; ++i) { union(connect[i][0], connect[i][1]); } // ne = Number of neutal groups // ma = Number of M influenced groups // pe = Number of P influenced groups int ne = 0, ma = 0, pe = 0; for(int i = 1; i <= n; ++i) { int x = parent(i); if (x == i) { if (sz[i][0] == sz[i][1]) { ne++; } else if (sz[i][0] > sz[i][1]) { ma++; } else { pe++; } } } Console.WriteLine("P = " + pe + "\nM = " + ma + "\nN = " + ne);}// Driver codestatic public void Main(){ // Nodes at each index ( 1 - base indexing ) List<char> nodes = new List<char>(){'P', 'M', 'P', 'M', 'P'}; // Connected Pairs List<List<int>> connect = new List<List<int>>(); connect.Add(new List<int>(){1, 3}); connect.Add(new List<int>(){3, 5}); connect.Add(new List<int>(){4, 5}); influenced(nodes, connect); }}// This code is contributed by rag2127 |
Javascript
<script>// Javascript implementation of the approach// To store the parents// of the current nodelet par = [];// To store the size of M and Plet sz = [];// Function for initializationfunction init(nodes){ // Size of the graph let n = nodes.length; for(let i = 0; i <= n; ++i) { par.push(i); if (i == 0) { sz.push([0,0]); } if (i > 0) { // If the node is P if (nodes[i - 1] == 'P') { sz.push([0,1]); } // If the node is M else { sz.push([1,0]); } } }}// To find the parent of// the current nodefunction parent(i){ while (par[i] != i) { i = par[i]; } return i;}// Merge functionfunction union(a,b){ a = parent(a); b = parent(b); if (a == b) { return; } // Total size by adding number // of M and P let sz_a = sz[a][0] + sz[a][1]; let sz_b = sz[b][0] + sz[b][1]; if (sz_a < sz_b) { let temp = a; a = b; b = temp; } par[b] = a; sz[a][0] = sz[a][0] + sz[b][0]; sz[a][1] = sz[a][1] + sz[b][1]; return;}// Function to calculate the influenced valuefunction influenced(nodes,connect){ // Number of nodes let n = nodes.length; // Initialization function init(nodes); // Size of the connected vector let k = connect.length; // Performing union operation for(let i = 0; i < k; ++i) { union(connect[i][0], connect[i][1]); } // ne = Number of neutal groups // ma = Number of M influenced groups // pe = Number of P influenced groups let ne = 0, ma = 0, pe = 0; for(let i = 1; i <= n; ++i) { let x = parent(i); if (x == i) { if (sz[i][0] == sz[i][1]) { ne++; } else if (sz[i][0] > sz[i][1]) { ma++; } else { pe++; } } } document.write("P = " + pe + "<br>M = " + ma + "<br>N = " + ne);}// Driver code// Nodes at each index ( 1 - base indexing )let nodes =[];nodes.push('P');nodes.push('M');nodes.push('P');nodes.push('M');nodes.push('P');// Connected Pairslet connect = [];connect.push([1,3]);connect.push([3,5]);connect.push([4,5]);influenced(nodes, connect);// This code is contributed by patel2127</script> |
Output:
P = 1 M = 1 N = 0
Time Complexity: O(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
