Given an integer N denoting the total number of fights between empire A and B all together in a war zone, also given a 2-D array arr of size N denoting that soldier arr[i][0] and arr[i][1] are fighting with each other. The task is to find the maximum number of soldiers belonging to an empire if it is possible to distribute all the soldiers among A and B, otherwise print -1.
Example:
Input: N = 4, arr = [[1, 2], [2, 3], [2, 4], [2, 5]]
Output: 4
Explanation: From the input we have following fight:
{1, 3, 4, 6} fighting with {2} => maximum group of soldier = 4.Input: N = 8, arr = [[1, 2], [2, 3], [3, 4], [3, 5], [6, 7], [7, 8], [7, 9], [7, 10]]
Output: 7
Explanation: From the input we have following fights:
{1, 3} fighting with {2, 4, 5} => maximum group of soldier=3
{6, 8, 9, 10} fighting with {7} => maximum group of soldier=4
Hence maximum number of soldier in an empire = 3+4 = 7Input: N=3, arr=[[1, 2], [2, 3], [3, 1]]
Output: -1
Explanation: it is impossible to distribute 1, 2 and 3 among A and B such that there is not a fight between soldier of same empire.
Approach: Using a Bipartite graph to solve the question as discussed below:
We can create a graph from the array ‘arr‘ such that there is a bidirectional edge between arr[i][0] and arr[i][1] , then apply the Bipartite coloring on each component of the graph.
To get the answer pick the occurrence of the maximum occurring color of each component of the graph and add them together.
If in case for any component we can not color it using Bipartite coloring, then we return -1.
Illustration:
Lets suppose, N=8, arr=[[1, 2],[1, 3],[1, 4],[1, 5],[2, 6],[3, 6],[4, 6],[5, 6]]
To solve this test case, firstly we can create a graph such that there is a bidirectional edge between arr[i][0] and arr[i][1] as shown in fig-1.
After applying Bipartite coloring on the graph (as shown in fig-1) we see that vertex {1, 6} have same color(blue) and vertex {2, 3, 4, 5} have same color(yellow). Since the frequency of Yellow color is more i.e. 4>2, hence for this graph we can conclude that maximum 4 number of soldier are in same team and return 4 as our answer.
fig-1
Now let’s see a case when grouping of soldier into two empiers is immpossible and we return -1 as our answer. Suppose N=5, arr=[[1, 2],[2, 3],[3, 4],[4, 5],[5, 1]]
In this test case when when we apply Bipartite coloring (say on vertex 1) there will be 2 cases of coloring possible:
Case 1: node 4 and node 5 have same color and an edge between them.
Case 2: node 4 and node 3 have same color and an edge between them.
Both these cases are contradicting the Bipartite coloring and hence we return -1. In short Bipartite coloring is impossible for a graph having an odd length cycle. This case is clearly shown in fig-2.
fig-2
Follow the steps to solve the problem:
- Create a graph ‘g‘ such that arr[i][0] and arr[i][1] are vertices of that graph.
- Keep track of all unique vertices in an array of ‘soldiers[]‘.
- Create a ‘colr[]‘ array initialized by ‘-1′ to keep track of the color of each vertex.
- Now apply Bipartite coloring on all the vertices which are not colored yet. For each component of the graph find the maximum occurrence of the color i.e. max(zero, one) (Note: zero and one represent two colors) and add that value to the answer ‘ans‘.
- In case Bipartite coloring is not possible for any component set the ‘flag’ variable as false and return ‘-1′.
Below is the implementation of the above algorithm:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// one and zero are our two colorsint one, zero;// Flag to check whether the answer// exists or notbool flag = true;void BipartiteColor(int v, vector<vector<int> >& g, vector<int>& colr, int paint){ // if the vertex is already colored if (colr[v] != -1) { // if previous color and current paint // contradict each other then our answer // won't exist if (colr[v] != paint) flag = false; return; } // paint the current vertex v colr[v] = paint; // if paint is 1 if (paint) one++; // if paint is 0 else zero++; // Recursive calls on the child of vertex v for (auto child : g[v]) { // Giving the complementory color to the // child i.e. if colr[v]=1 then // colr[child]=0 and vice verse BipartiteColor(child, g, colr, !paint); }}void maximumSoldier(int N, vector<vector<int> > arr){ // Creating a graph // taking 20001 as the upper bound // for unique soldiers. vector<vector<int> > g(20001); // set to store all the unique soldiers set<int> st; for (int i = 0; i < N; i++) { // u and v stores the soldier int u, v; u = arr[i][0]; v = arr[i][1]; // Initializing the graph g[u].push_back(v); g[v].push_back(u); // Inserting u and v into set st.insert(u); st.insert(v); } // To store all the unique // soldiers of set st vector<int> soldiers; for (auto e : st) soldiers.push_back(e); // Initializing the result as ans=0 int ans = 0; // colr[] to apply Bipartite coloring vector<int> colr(20001, -1); // Loop for each soldier for (auto e : soldiers) { // if already colored we continue; if (colr[e] != -1) continue; // one and zero are our two colors. one = 0; zero = 0; // Applying Bipartite Coloring BipartiteColor(e, g, colr, 0); // Updating our answer ans += max(one, zero); } if (flag) cout << ans; else cout << -1;}// Driver Codeint main(){ // Input test case int N = 4; vector<vector<int> > arr = { { 1, 2 }, { 2, 3 }, { 2, 4 }, { 2, 5 } }; // Function call maximumSoldier(N, arr); return 0;} |
Java
//Java code for the above approachimport java.util.*;public class GFG { // one and zero are our two colors static int one, zero; // Flag to check whether the answer // exists or not static boolean flag = true; static void BipartiteColor(int v, List<List<Integer>> g, List<Integer> colr, int paint) { // if the vertex is already colored if (colr.get(v) != -1) { // if previous color and current paint // contradict each other then our answer // won't exist if (colr.get(v) != paint) flag = false; return; } // paint the current vertex v colr.set(v, paint); // if paint is 1 if (paint == 1) one++; // if paint is 0 else zero++; // Recursive calls on the child of vertex v for (int child : g.get(v)) { // Giving the complementary color to the // child i.e. if colr[v]=1 then // colr[child]=0 and vice versa BipartiteColor(child, g, colr, (paint == 1) ? 0 : 1); } } static void maximumSoldier(int N, List<List<Integer>> arr) { // Creating a graph // taking 20001 as the upper bound // for unique soldiers. List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < 20001; i++) { g.add(new ArrayList<>()); } // set to store all the unique soldiers Set<Integer> st = new HashSet<>(); for (int i = 0; i < N; i++) { // u and v stores the soldier int u, v; u = arr.get(i).get(0); v = arr.get(i).get(1); // Initializing the graph g.get(u).add(v); g.get(v).add(u); // Inserting u and v into set st.add(u); st.add(v); } // To store all the unique // soldiers of set st List<Integer> soldiers = new ArrayList<>(st); // Initializing the result as ans=0 int ans = 0; // colr[] to apply Bipartite coloring List<Integer> colr = new ArrayList<>(Collections.nCopies(20001, -1)); // Loop for each soldier for (int e : soldiers) { // if already colored we continue; if (colr.get(e) != -1) continue; // one and zero are our two colors. one = 0; zero = 0; // Applying Bipartite Coloring BipartiteColor(e, g, colr, 0); // Updating our answer ans += Math.max(one, zero); } if (flag) System.out.println(ans); else System.out.println(-1); } // Driver Code public static void main(String[] args) { // Input test case int N = 4; List<List<Integer>> arr = new ArrayList<>(); arr.add(Arrays.asList(1, 2)); arr.add(Arrays.asList(2, 3)); arr.add(Arrays.asList(2, 4)); arr.add(Arrays.asList(2, 5)); // Function call maximumSoldier(N, arr); }} |
Python3
# Python code for the above approach : # Function to perform Bipartite Coloringdef bipartite_color(v, g, colr, paint): global one, zero, flag # If the vertex is already colored if colr[v] != -1: # If the previous color and current paint # contradict each other, then our answer # won't exist if colr[v] != paint: flag = False return # Paint the current vertex v colr[v] = paint # If paint is 1 if paint: one += 1 # If paint is 0 else: zero += 1 # Recursive calls on the child of vertex v for child in g[v]: # Giving the complementary color to the # child, i.e., if colr[v]=1 then # colr[child]=0 and vice versa bipartite_color(child, g, colr, not paint)# Function to find the maximum number of soldiersdef maximum_soldier(N, arr): global one, zero, flag # Creating a graph with an upper bound of 20001 g = [[] for _ in range(20001)] # Set to store all the unique soldiers st = set() for i in range(N): # u and v store the soldier u, v = arr[i][0], arr[i][1] # Initializing the graph g[u].append(v) g[v].append(u) # Inserting u and v into the set st.add(u) st.add(v) # To store all the unique soldiers from the set soldiers = list(st) # Initializing the result as ans=0 ans = 0 # colr[] to apply Bipartite coloring colr = [-1] * 20001 # Loop for each soldier for e in soldiers: # If already colored, continue if colr[e] != -1: continue # one and zero are our two colors one = 0 zero = 0 # Applying Bipartite Coloring bipartite_color(e, g, colr, 0) # Updating our answer ans += max(one, zero) if flag: print(ans) else: print(-1)if __name__ == "__main__": # Input test case N = 4 arr = [[1, 2], [2, 3], [2, 4], [2, 5]] flag = True # Function call maximum_soldier(N, arr) # this code is contributed by uttamdp_10 |
C#
//Java code for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG{ // one and zero are our two colors static int one, zero; // Flag to check whether the answer // exists or not static bool flag = true; static void BipartiteColor(int v, List<List<int>> g, List<int> colr, int paint) { // If the vertex is already colored if (colr[v] != -1) { // If previous color and current paint // contradict each other then our answer // won't exist if (colr[v] != paint) flag = false; return; } // Paint the current vertex v colr[v] = paint; // If paint is 1 if (paint == 1) one++; // If paint is 0 else zero++; // Recursive calls on the child of vertex v foreach (int child in g[v]) { // Giving the complementary color to the // child, i.e. if colr[v] = 1 then // colr[child] = 0 and vice versa BipartiteColor(child, g, colr, (paint == 1) ? 0 : 1); } } static void MaximumSoldier(int N, List<List<int>> arr) { // Creating a graph // taking 20001 as the upper bound // for unique soldiers. List<List<int>> g = new List<List<int>>(); for (int i = 0; i < 20001; i++) { g.Add(new List<int>()); } // Set to store all the unique soldiers HashSet<int> st = new HashSet<int>(); for (int i = 0; i < N; i++) { // u and v stores the soldier int u, v; u = arr[i][0]; v = arr[i][1]; // Initializing the graph g[u].Add(v); g[v].Add(u); // Inserting u and v into set st.Add(u); st.Add(v); } // To store all the unique // soldiers of set st List<int> soldiers = st.ToList(); // Initializing the result as ans = 0 int ans = 0; // colr[] to apply Bipartite coloring List<int> colr = Enumerable.Repeat(-1, 20001).ToList(); // Loop for each soldier foreach (int e in soldiers) { // if already colored we continue; if (colr[e] != -1) continue; // one and zero are our two colors. one = 0; zero = 0; // Applying Bipartite Coloring BipartiteColor(e, g, colr, 0); // Updating our answer ans += Math.Max(one, zero); } if (flag) Console.WriteLine(ans); else Console.WriteLine(-1); } // Driver Code public static void Main(string[] args) { // Input test case int N = 4; List<List<int>> arr = new List<List<int>> { new List<int> { 1, 2 }, new List<int> { 2, 3 }, new List<int> { 2, 4 }, new List<int> { 2, 5 } }; // Function call MaximumSoldier(N, arr); }} |
Javascript
// Bipartite graph coloring variableslet one, zero;let flag = true;function bipartiteColor(v, g, colr, paint) { // If the vertex is already colored if (colr[v] !== -1) { // If previous color and current paint contradict each other // then our answer won't exist if (colr[v] !== paint) { flag = false; } return; } colr[v] = paint; if (paint === 1) { one++; } else { zero++; } for (const child of g[v]) { // Giving the complementary color to the child // If colr[v] = 1, then colr[child] = 0 and vice versa bipartiteColor(child, g, colr, paint === 1 ? 0 : 1); }}function maximumSoldier(N, arr) { // Creating a graph const g = new Array(20001).fill(null).map(() => []); const st = new Set(); for (let i = 0; i < N; i++) { // u and v store the soldiers const u = arr[i][0]; const v = arr[i][1]; // Initializing the graph g[u].push(v); g[v].push(u); // Inserting u and v into the set st.add(u); st.add(v); } // Convert the set to an array of unique soldiers const soldiers = [...st]; // Initialize the result as ans = 0 let ans = 0; // Array colr[] to apply Bipartite coloring const colr = new Array(20001).fill(-1); // Loop for each soldier for (const e of soldiers) { // If already colored, continue if (colr[e] !== -1) { continue; } one = 0; zero = 0; // Applying Bipartite Coloring bipartiteColor(e, g, colr, 0); // Updating the answer ans += Math.max(one, zero); } if (flag) { console.log(ans); } else { console.log(-1); }}// Input test caseconst N = 4;const arr = [ [1, 2], [2, 3], [2, 4], [2, 5]];// Function callmaximumSoldier(N, arr); |
4
Time Complexity: O(N*logN + N*(V+E)), where N is the size of arr[], V is the unique number of soldiers(vertices) and E is the total edges in the graph.
Auxiliary Space: O(V), where V is the unique number of soldiers(vertices)
