![[Solved] Major Count Contest Problem](https://realcoder.techss24.com/wp-content/uploads/2022/06/Solved-Major-Count-Contest-Problem.png "[Solved] Major Count Contest Problem")
Major Count: Ninja A and Ninja B want to play a game on a graph.
They have an undirected graph with ‘N’ vertices and each pair of vertices is connected by atmost one edge and there are no self-loops.
There are exactly ‘P’ edges that are owned by Ninja A and exactly ‘Q’ edges that are owned by Ninja B.
Your task is to find the tree with all vertices which have a minimum number of edges owned by Ninja A and you have to return that number else return -1 if there is no tree found which connects all vertices.
Major Count Contest Problem
Input Format :
The first line contains a single integer ‘T’, denoting the number of test cases. The test cases are as follows. The first line of each test case contains three space-separated integers, ‘N’, ‘P’ and ‘Q’, denoting the number of nodes, the number of edges owned by Ninja A and the number of edges owned by Ninja B. Next ‘P’ lines contain two space-separated integers ‘u’ and ‘v’, where the edge between node ‘u’ and ‘v’ is owned by Ninja A. Next ‘Q’ lines contain two space-separated integers ‘u’ and ‘v’, where the edge between node ‘u’ and ‘v’ is owned by Ninja B.
Output Format :
For each test case, return the minimum number of edges that are owned by Ninja A and -1 if there is no tree found with all vertices.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10 0 <= N <= 10^5 0 <= P + Q <= min( 10^5, N * (N - 1) / 2 ) The sum of 'N' over all test cases does not exceed 10^5. Time Limit: 1 sec
Sample Input 1 :
2 5 4 4 1 2 3 2 5 2 4 2 1 3 4 3 5 3 1 4 3 1 2 1 3 1 2 2 3
Sample Output 1 :
1 0
Explanation Of Sample Input 1 :
For test case 1,
One of the possible solution is
![[Solved] Major Count Contest Problem](https://files.codingninjas.in/q_img-16781.png "[Solved] Major Count Contest Problem")
The edge of Ninja B is (1,3), (3,4), and (3,5).
The edge of Ninja A is (3,2).
For test case 2,
The edge of Ninja B is (1,3), and (2,3).
Sample Input 2 :
2 4 1 1 1 2 1 3 1 0 0
Sample Output 2 :
-1 0
Solution
MST(Kruskal’s algorithm)
Approach:
This problem can be converted to a minimum spanning tree as we use the weight of the edge owned by Ninja A as 1 and Ninja B as 0 and find the value of the minimum spanning tree of the entire graph and the value of this MST is the number of edges used that are owned by Ninja A.
Algorithm:
- Initialize the integer ‘N’, ‘P’, ‘Q’
- Create an adjacencies vector of length P + Q and store all the given pair of vertices.
- Initialize the DSU.
- Now iterate through every edge of Ninja ‘B’ and join them if they are not already joined by checking in DSU.
- Then iterate through every edge of Ninja ‘A’ and join them if not already joined and it will cost 1 unit to join.
- At the end check whether all vertices are connected in a single tree or not.
- Then the answer will be the total cost of this tree.
Time Complexity
O( M * log( N ) ), where ‘N’ and ‘M’ denote the number of vertices and the sum of edges of Ninja ‘A’ and Ninja ‘B’, respectively.
We are using DSU. Hence, the overall complexity is O(M * log(N)).
Space Complexity
O( M + N ), where ‘N’ and ‘M’ denote the number of vertices and the sum of edges of Ninja ‘A’ and ninja ‘B’, respectively.
We are storing all the edges and storing all the vertices to keep track in DSU. Hence, the overall complexity is O( M + N ).
/*
Time Complexity: O( M * log(N) )
Space Complexity: O( N )
where 'M' and N' are the number of edge and vertices respectively.
*/
// DSU
// Finding the parent.
int find_par(int v, vector<int>& parent)
{
if (v == parent[v])
return v;
return parent[v] = find_par(parent[v] , parent);
}
// Merging node a and b.
void union_sets(int a, int b, vector<int>& parent, vector<int>& _rank)
{
a = find_par(a , parent);
b = find_par(b , parent);
// If they are not already connected.
if (a != b)
{
if (_rank[a] < _rank[b])
swap(a, b);
parent[b] = a;
_rank[a] += _rank[b];
}
}
int minEdge(int n, int p, int q, vector<pair<int, int> > adj)
{
vector<int> parent(n + 1), _rank(n + 1);
int cost = 0;
// initializing DSU.
for (int i = 1; i < n + 1; i++)
{
parent[i] = i;
_rank[i] = 1;
}
// Merging for all edge of Ninja B which is from index 'p' to 'p + q' in adj vector.
for (int i = p; i < p + q; i++)
{
// To check if it is already connected or not.
if (find_par(adj[i].first, parent) != find_par(adj[i].second, parent))
{
cost += 0;
union_sets(adj[i].first, adj[i].second, parent, _rank);
}
}
// Merging for all edge of Ninja A.
for (int i = 0; i < p; i++)
{
if (find_par(adj[i].first, parent) != find_par(adj[i].second, parent))
{
cost += 1;
union_sets(adj[i].first, adj[i].second, parent, _rank);
}
}
// Check if all vertices are connected.
if (_rank[find_par(1, parent)] != n && n > 1)
return -1;
else
return cost;
}/*
Time Complexity: O( M * log(N) )
Space Complexity: O( N )
where 'M' and N' are the number of edge and vertices respectively.
*/
public class Solution {
// DSU
// Finding the parent.
private static int find_par(int v, int[] parent)
{
if (v == parent[v])
return v;
return parent[v] = find_par(parent[v] , parent);
}
// Merging node a and b.
private static void union_sets(int a, int b, int[] parent, int[] _rank)
{
a = find_par(a , parent);
b = find_par(b , parent);
// If they are not already connected.
if (a != b)
{
if (_rank[a] < _rank[b]){
int temp = b;
b = a;
a = temp;
}
parent[b] = a;
_rank[a] += _rank[b];
}
}
public static int minEdge(int n, int p, int q, int[][] adj)
{
int[] parent = new int[n + 1], _rank = new int[n + 1];
int cost = 0;
// initializing DSU
for (int i = 1; i < n + 1; i++)
{
parent[i] = i;
_rank[i] = 1;
}
// Merging for all edge of Ninja B which is from index 'p' to 'p + q' in adj vector.
for (int i = p; i < p + q; i++)
{
// To check if it is already connected or not.
if (find_par(adj[i][0], parent) != find_par(adj[i][1], parent))
{
cost += 0;
union_sets(adj[i][0], adj[i][1], parent, _rank);
}
}
// Merging for all edge of Ninja A
for (int i = 0; i < p; i++)
{
if (find_par(adj[i][0], parent) != find_par(adj[i][1], parent))
{
cost += 1;
union_sets(adj[i][0], adj[i][1], parent, _rank);
}
}
// Check if all vertices are connected.
if (_rank[find_par(1, parent)] != n && n > 1){
return -1;
}
else {
return cost;
}
}
}"""
Time Complexity: O( M * log(N) )
Space Complexity: O( N )
where 'M' and N' are the number of edge and vertices respectively.
"""
# DSU
# Finding the parent.
def find_par(v, parent):
if v == parent[v]:
return v
parent[v] = find_par(parent[v], parent)
return parent[v]
# Merging node a and b.
def union_sets(a, b, parent, _rank):
a = find_par(a, parent)
b = find_par(b, parent)
# If they are not already connected.
if a != b:
if _rank[a] < _rank[b]:
a, b = b, a
parent[b] = a
_rank[a] += _rank[b]
def minEdge(n, p, q, adj):
parent = [0] * (n + 1)
_rank = [0] * (n + 1)
cost = 0
# initializing DSU.
i = 1
while i < n + 1:
parent[i] = i
_rank[i] = 1
i += 1
# Merging for all edge of Ninja B which is from index 'p' to 'p + q' in adj vector.
i = p
while i < p + q:
# To check if it is already connected or not.
if find_par(adj[i][0], parent) != find_par(adj[i][1], parent):
cost += 0
union_sets(adj[i][0], adj[i][1], parent, _rank)
i += 1
# Merging for all edge of Ninja A.
for i in range(0, p):
if find_par(adj[i][0], parent) != find_par(adj[i][1], parent):
cost += 1
union_sets(adj[i][0], adj[i][1], parent, _rank)
# Check if all vertices are connected.
if _rank[find_par(1, parent)] != n and n > 1:
return -1
else:
return costHappy Learning – If you require any further information, feel free to contact me.
![[Solved] First and Last Position of an Element In Sorted Array](https://realcoder.techss24.com/wp-content/uploads/2022/06/Solved-First-and-Last-Position-of-an-Element-In-Sorted-Array-300x200.png)
![[Solved] Basketball Players Contest Problem](https://realcoder.techss24.com/wp-content/uploads/2022/06/Solved-Basketball-Players-Contest-Problem-300x200.png)