Given an integer N, denoting the total number of nodes in a graph without any edges, you have to process Q queries of the form u, v denoting that you have to add an edge between node u and v, after each query you have to print the size difference between largest component and the smallest component of the graph.
Examples:
Input: N = 2, Q = 1, queries = [[1, 2]]
Output: 0
Explanation:
- Initial components = {{1}{2}}
- After query[0]:
- we have components = {{1, 2}}, Since we have only one component of size 2, the difference is 2-2 = 0.
Input: N = 4, Q = 2, queries = [[1, 2],[2, 4]]
Output: [1, 2]
Explanation:
- Initial components = {{1},{2},{3},{4}},
- After query[0]:
- we have components = {{1, 2},{3},{4}} , So difference is, 2-1 = 1.
- After query[1]:
- we have components = {{1, 2, 4},{3}} , So difference is, 3-1 = 2.
Approach: We can use Disjoint-Set-Union(DSU) and Priority Queue(using multiset) to solve this question as discussed below:
For each query of adding an edge between ‘u‘ and ‘v’ we can use DSU to put both the nodes in the same set and update the size of the set they are in. Now we can put this new size in our multiset and remove the older sizes from it.
Simply print the difference between the maximum and minimum element of the multiset to get the answer for each query.
Firstly we have to construct our DSU functions as per the below steps:
- Create a parent array of the size N i.e. the total number of nodes. This array will denote the parent of each node(component).
- make(int i): Initialize parent[i]=i, sizez[i]=1, and for each i insert 1 inside a multiset ‘st’. This indicates that each node currently has size 1 and forms a component of its own.
- find(int v): finds the parent of the component the node ‘v‘ belongs to.
- Union(int a, int b): Merge the nodes ‘a‘ and ‘b‘ together. Delete the old sizes of ‘a‘ and ‘b‘ from the ‘st’ and insert the new size formed by the combination of ‘a‘ and ‘b‘
Now use the below algorithm to solve the problem:
- Initialize the DSU data structure for each node from 1 to N, using the make function.
- For each query, Union the nodes u and v.
- Print the difference between the back and front element of the ‘st‘.
below is the implementation of the above algorithm:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// parent array for DSU to keep track// of connected nodes having same parentint parent[1000];// DSU by size to speed up the// time complexityint sizes[1000];// A single multiset used as a min// as well as max heapmultiset<int> st;// This function is to initialize// DSU data structurevoid make(int i){ parent[i] = i; sizes[i] = 1; st.insert(1);}// This function is to return the// parent of a nodeint find(int v){ if (v == parent[v]) return v; return parent[v] = find(parent[v]);}// Union funtion to merge the components// of graph and to update the multiset(heap)void Union(int a, int b){ a = find(a); b = find(b); if (a != b) { if (sizes[a] < sizes[b]) swap(a, b); parent[b] = a; // Remove old size st.erase(st.find(sizes[a])); // Remove old size st.erase(st.find(sizes[b])); // Insert new updated size st.insert(sizes[a] + sizes[b]); sizes[a] += sizes[b]; }}// Driver Functionint main(){ int N = 4; int Q = 2; // Initialize DSU for each node // from 1 to N for (int i = 1; i <= N; i++) { make(i); } vector<vector<int> > queries = { { 1, 2 }, { 2, 4 } }; for (int i = 0; i < Q; i++) { int u = queries[i][0]; int v = queries[i][1]; // Union u and v, as we add // edge between them Union(u, v); // Using multiset as min heap // from front int a = *st.begin(); // Using multiset as max-heap // from back int b = *(--st.end()); cout << b - a << endl; }} |
Java
import java.util.*;public class GFG { // Parent array for DSU to keep track of connected nodes having the same parent static int[] parent = new int[1000]; // Sizes array to store the size of each component static int[] sizes = new int[1000]; // A single multiset used as a min as well as max heap static List<Integer> st = new ArrayList<>(); // Function to initialize DSU data structure static void make(int i) { parent[i] = i; sizes[i] = 1; st.add(1); } // Function to return the parent of a node with path compression static int find(int v) { if (v == parent[v]) { return v; } parent[v] = find(parent[v]); return parent[v]; } // Union function to merge the components of the graph and update the list (heap) static void union(int a, int b) { a = find(a); b = find(b); if (a != b) { if (sizes[a] < sizes[b]) { int temp = a; a = b; b = temp; } parent[b] = a; // Remove old size st.remove(Integer.valueOf(sizes[a])); // Remove old size st.remove(Integer.valueOf(sizes[b])); // Insert new updated size st.add(sizes[a] + sizes[b]); sizes[a] += sizes[b]; } } // Driver Function public static void main(String[] args) { int N = 4; int Q = 2; // Initialize DSU for each node from 1 to N for (int i = 1; i <= N; i++) { make(i); } int[][] queries = {{1, 2}, {2, 4}}; for (int i = 0; i < Q; i++) { int u = queries[i][0]; int v = queries[i][1]; // Union u and v, as we add an edge between them union(u, v); // Using list as min-heap int a = Collections.min(st); // Using list as max-heap int b = Collections.max(st); System.out.println(b - a); } }} |
Python3
# parent array for DSU to keep track# of connected nodes having same parentparent = [0] * 1000# DSU by size to speed up the# time complexitysizes = [0] * 1000# A single multiset used as a min# as well as max heapst = []# This function is to initialize# DSU data structuredef make(i): parent[i] = i sizes[i] = 1 st.append(1)# This function is to return the# parent of a nodedef find(v): if v == parent[v]: return v parent[v] = find(parent[v]) return parent[v]# Union function to merge the components# of the graph and to update the list (heap)def union(a, b): a = find(a) b = find(b) if a != b: if sizes[a] < sizes[b]: a, b = b, a parent[b] = a # Remove old size st.remove(sizes[a]) # Remove old size st.remove(sizes[b]) # Insert new updated size st.append(sizes[a] + sizes[b]) sizes[a] += sizes[b]# Driver Functionif __name__ == "__main__": N = 4 Q = 2 # Initialize DSU for each node # from 1 to N for i in range(1, N + 1): make(i) queries = [[1, 2], [2, 4]] for i in range(Q): u = queries[i][0] v = queries[i][1] # Union u and v, as we add # an edge between them union(u, v) # Using list as min-heap a = min(st) # Using list as max-heap b = max(st) print(b - a) |
C#
using System;using System.Collections.Generic;using System.Linq;public class GFG{ // Parent array for DSU to keep track of connected nodes having the same parent static int[] parent = new int[1000]; // Sizes array to store the size of each component static int[] sizes = new int[1000]; // A single multiset used as a min as well as max heap static List<int> st = new List<int>(); // Function to initialize DSU data structure static void Make(int i) { parent[i] = i; sizes[i] = 1; st.Add(1); } // Function to return the parent of a node with path compression static int Find(int v) { if (v == parent[v]) { return v; } parent[v] = Find(parent[v]); return parent[v]; } // Union function to merge the components of the graph and update the list (heap) static void Union(int a, int b) { a = Find(a); b = Find(b); if (a != b) { if (sizes[a] < sizes[b]) { int temp = a; a = b; b = temp; } parent[b] = a; // Remove old size st.Remove(sizes[a]); // Remove old size st.Remove(sizes[b]); // Insert new updated size st.Add(sizes[a] + sizes[b]); sizes[a] += sizes[b]; } } // Driver Function public static void Main(string[] args) { int N = 4; int Q = 2; // Initialize DSU for each node from 1 to N for (int i = 1; i <= N; i++) { Make(i); } int[][] queries = new int[][] { new int[] { 1, 2 }, new int[] { 2, 4 } }; for (int i = 0; i < Q; i++) { int u = queries[i][0]; int v = queries[i][1]; // Union u and v, as we add an edge between them Union(u, v); // Using list as min-heap int a = st.Min(); // Using list as max-heap int b = st.Max(); Console.WriteLine(b - a); } }} |
Javascript
// Parent array for DSU to keep track of connected nodes having the same parentconst parent = new Array(1000);for (let i = 0; i < parent.length; i++) { parent[i] = i;}// Sizes array to store the size of each componentconst sizes = new Array(1000).fill(1);// A single multiset used as a min as well as max heapconst st = [];// Function to initialize DSU data structurefunction make(i) { parent[i] = i; sizes[i] = 1; st.push(1);}// Function to return the parent of a node with path compressionfunction find(v) { if (v === parent[v]) { return v; } parent[v] = find(parent[v]); return parent[v];}// Union function to merge the components of the graph and update the list (heap)function union(a, b) { a = find(a); b = find(b); if (a !== b) { if (sizes[a] < sizes[b]) { [a, b] = [b, a]; // Swap a and b } parent[b] = a; // Remove old size st.splice(st.indexOf(sizes[a]), 1); // Remove old size st.splice(st.indexOf(sizes[b]), 1); // Insert new updated size st.push(sizes[a] + sizes[b]); sizes[a] += sizes[b]; }}// Driver Functionfunction main() { const N = 4; const Q = 2; // Initialize DSU for each node from 1 to N for (let i = 1; i <= N; i++) { make(i); } const queries = [[1, 2], [2, 4]]; for (let i = 0; i < Q; i++) { const u = queries[i][0]; const v = queries[i][1]; // Union u and v, as we add an edge between them union(u, v); // Using array as min-heap const a = Math.min(...st); // Using array as max-heap const b = Math.max(...st); console.log(b - a); }}main(); |
Output
1 2
Time Complexity: O(Q(logN) + N), where Q is the number of queries and N is the number of nodes.
Auxiliary Space: O(N), where N is the number of nodes.
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
