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 which denotes that you have to add an edge between node u and v. After each query you have to print the minimum difference possible between the size any two components of the graph. If there is only one component simply print 0.
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, simply print 0.
Input: N = 4, Q = 2, queries = [[1 2], [2 4]]
Output: [0, 2]
Explanation:
- Initial components = {{1}, {2}, {3}, {4}}
- After query[0]:
- we have components={{1 2}, {3}, {4}}
- So minimum difference = size of {3} – size of {4} = 1-1 = 0.
- After query[1]:
- We have components={{1 2 4},{3}}
- So minimum difference = size of {1 2 4} – size of {3} = 3 – 1 = 2.
Efficient Approach: We can use Disjoint-Set_Union(DSU) and Set data structure to solve this question optimally as discussed below.
For each query of creating an edge between node ‘u’ and ‘v’ , we can use Union operation of DSU to merge both the nodes into a same component. Also we can use a set to remove older sizes of the component and insert new sizes efficiently . This set will provide a sorted information about the sizes of each component existing in the graph.
Answer for each query can be obtained by 2 cases.
Case 1: If any element of the set has a frequency > 1
- Simply print 0, as we have 2 component of same size.
Case 2: If all the element in the set has frequency<=1
- Print the minimum among all the differences between adjacent elements in the sorted-set while iterating.
Follow the below steps to solve the problem:
- Create a set ‘st‘ and frequency array ‘freq‘ to store the information about the sizes of the component existing in the graph
- For each query merge the nodes ‘u‘ and ‘v‘ using the Union operation of DSU.
- Update the ‘st’ and ‘freq’, by deleting the older component sizes and inserting the new component sizes.
- Iterate the elements of the set and find the answer ‘ans‘ by the following comparison:
- If freq[element]>1 : ans=0 , break out of the iteration
- Else ans = minimum of all the differences between the consecutive elements of set iteration.
Below is the implementation of the above algorithm:
C++
// Below is the C++ code for above approach#include <bits/stdc++.h>#define ll long longusing namespace std;// parent array to store the parent of each// component of the graphll parent[100010];// Array used to apply DSU by size in order// to fasten the DSU functionsll sizez[100010];// Frequency array to optimize the find the// frequency of size of components in the graphll freq[100010];// set to store different sizes of the componentset<ll> st;// This function is used to initialize our DSU// data structurevoid make(ll i){ parent[i] = i; sizez[i] = 1; freq[1]++;}// This function is used to find the parent of// each component of the graphll find(ll v){ if (v == parent[v]) return v; // Path compression // technique of DSU return parent[v] = find(parent[v]);}// This function is used to Merge two components// together it also updates our frequency array// and set with new sizes and removes older sizesvoid Union(ll a, ll b){ a = find(a); b = find(b); if (a != b) { if (sizez[a] < sizez[b]) swap(a, b); // Decreasing the frequency of older size freq[sizez[a]]--; // Removing the older size if frequency // reaches to 0 if (freq[sizez[a]] == 0) st.erase(st.find(sizez[a])); // Decreasing the frequency of older size freq[sizez[b]]--; // Removing the older size if frequency // reaches to 0 if (freq[sizez[b]] == 0) st.erase(st.find(sizez[b])); parent[b] = a; sizez[a] += sizez[b]; // Incrementing the frequency of new size freq[sizez[a]]++; // Inserting the new size in the set if (freq[sizez[a]] == 1) st.insert(sizez[a]); }}// Driver Functionint main(){ ll N, Q; N = 4; Q = 2; vector<vector<int> > queries = { { 1, 2 }, { 2, 4 } }; // Initial component size is 1 st.insert(1); // Initialize our DSU for (int i = 1; i <= N; i++) { make(i); } for (int i = 0; i < Q; i++) { ll u = queries[i][0]; ll v = queries[i][1]; Union(u, v); ll ans = INT_MAX; ll pre = INT_MIN; // Finding the minimum difference between // adjacent element of sorted set for (auto e : st) { // If any element has frequency greater // than 1, answer will be 0 if (freq[e] > 1) { ans = 0; break; } ans = min(ans, e - pre); pre = e; } if (ans == INT_MAX) ans = 0; cout << ans << endl; }} |
Java
// Below is the Java code for above approachimport java.util.*;public class Main { // parent array to store the parent of each// component of the graph static int[] parent; // Array used to apply DSU by size in order// to fasten the DSU functions static int[] sizez; // Frequency array to optimize the find the// frequency of size of components in the graph static int[] freq; // set to store different sizes of the component static TreeSet<Integer> st; // This function is used to initialize our DSU// data structure static void make(int i) { parent[i] = i; sizez[i] = 1; freq[1]++; } // This function is used to find the parent of// each component of the graph static int find(int v) { if (v == parent[v]) return v; // Path compression // technique of DSU return parent[v] = find(parent[v]); } // This function is used to Merge two components// together it also updates our frequency array// and set with new sizes and removes older sizes static void Union(int a, int b) { a = find(a); b = find(b); if (a != b) { if (sizez[a] < sizez[b]) { int temp = a; a = b; b = temp; } // Decreasing the frequency of older size freq[sizez[a]]--; if (freq[sizez[a]] == 0) st.remove(sizez[a]); // Removing the older size if frequency // reaches to 0 freq[sizez[b]]--; if (freq[sizez[b]] == 0) st.remove(sizez[b]); parent[b] = a; sizez[a] += sizez[b]; // Incrementing the frequency of new size freq[sizez[a]]++; // Inserting the new size in the set if (freq[sizez[a]] == 1) st.add(sizez[a]); } } // Driver code public static void main(String[] args) { // input int N = 4; int Q = 2; int[][] queries = { { 1, 2 }, { 2, 4 } }; // Initial component size is 1 st = new TreeSet<>(); st.add(1); parent = new int[N + 1]; sizez = new int[N + 1]; freq = new int[N + 1]; // Initialize our DSU for (int i = 1; i <= N; i++) { make(i); } // Finding the minimum difference between // adjacent element of sorted set for (int i = 0; i < Q; i++) { int u = queries[i][0]; int v = queries[i][1]; Union(u, v); int ans = Integer.MAX_VALUE; int pre = Integer.MIN_VALUE; for (int e : st) { // If any element has frequency greater // than 1, answer will be 0 if (freq[e] > 1) { ans = 0; break; } if (pre != Integer.MIN_VALUE) { ans = Math.min(ans, e - pre); } pre = e; } System.out.println(ans); } }} |
Python3
# Below is the Python code for above approach# Initialize parent array to store the parent of each # component of the graphparent = [0] * 100010# Array used to apply DSU by size in order# to fasten the DSU functionssizez = [0] * 100010# Frequency array to optimize finding the # frequency of component sizes in the graphfreq = [0] * 100010# Set to store different sizes of the componentsst = set()# This function initializes the DSU # data structuredef make(i): parent[i] = i sizez[i] = 1 freq[1] += 1# This function finds the parent of each # component in the graph using path compressiondef find(v): if v == parent[v]: return v parent[v] = find(parent[v]) return parent[v]# This function is used to Merge two components# together it also updates our frequency array# and set with new sizes and removes older sizesdef Union(a, b): a = find(a) b = find(b) if a != b: if sizez[a] < sizez[b]: a, b = b, a # Decrease the frequency of older size freq[sizez[a]] -= 1 # Remove the older size if frequency reaches 0 if freq[sizez[a]] == 0: st.remove(sizez[a]) # Decrease the frequency of older size freq[sizez[b]] -= 1 # Remove the older size if frequency reaches 0 if freq[sizez[b]] == 0: st.remove(sizez[b]) parent[b] = a sizez[a] += sizez[b] # Increment the frequency of new size freq[sizez[a]] += 1 # Insert the new size into the set if freq[sizez[a]] == 1: st.add(sizez[a])# Driver CodeN, Q = 4, 2queries = [[1, 2], [2, 4]]# Initial component size is 1st.add(1)# Initialize our DSUfor i in range(1, N + 1): make(i)for i in range(Q): u, v = queries[i] Union(u, v) ans = float('inf') pre = float('-inf') # Finding the minimum difference between # adjacent elements of the sorted set for e in sorted(st): # If any element has frequency greater # than 1, the answer will be 0 if freq[e] > 1: ans = 0 break ans = min(ans, e - pre) pre = e if ans == float('inf'): ans = 0 print(ans)# This code is contributed by Prasad |
C#
using System;using System.Collections.Generic;class MainClass{ // parent array to store the parent of each // component of the graph static long[] parent = new long[100010]; // Array used to apply DSU by size in order // to fasten the DSU functions static long[] sizez = new long[100010]; // Frequency array to optimize the find the // frequency of size of components in the graph static long[] freq = new long[100010]; // set to store different sizes of the component static SortedSet<long> st = new SortedSet<long>(); // This function is used to initialize our DSU // data structure static void make(long i) { parent[i] = i; sizez[i] = 1; freq[1]++; } // This function is used to find the parent of // each component of the graph static long find(long v) { if (v == parent[v]) return v; // Path compression // technique of DSU return parent[v] = find(parent[v]); } // This function is used to Merge two components // together it also updates our frequency array // and set with new sizes and removes older sizes static void Union(long a, long b) { a = find(a); b = find(b); if (a != b) { if (sizez[a] < sizez[b]) (a, b) = (b, a); // Decreasing the frequency of older size freq[sizez[a]]--; // Removing the older size if frequency // reaches to 0 if (freq[sizez[a]] == 0) st.Remove(sizez[a]); // Decreasing the frequency of older size freq[sizez[b]]--; // Removing the older size if frequency // reaches to 0 if (freq[sizez[b]] == 0) st.Remove(sizez[b]); parent[b] = a; sizez[a] += sizez[b]; // Incrementing the frequency of new size freq[sizez[a]]++; // Inserting the new size in the set if (freq[sizez[a]] == 1) st.Add(sizez[a]); } } // Driver Function public static void Main(string[] args) { long N, Q; N = 4; Q = 2; List<List<long>> queries = new List<List<long>> { new List<long> { 1, 2 }, new List<long> { 2, 4 } }; // Initial component size is 1 st.Add(1); // Initialize our DSU for (int i = 1; i <= N; i++) { make(i); } for (int i = 0; i < Q; i++) { long u = queries[i][0]; long v = queries[i][1]; Union(u, v); long ans = int.MaxValue; long pre = int.MinValue; // Finding the minimum difference between // adjacent element of sorted set foreach (var e in st) { // If any element has frequency greater // than 1, answer will be 0 if (freq[e] > 1) { ans = 0; break; } ans = Math.Min(ans, e - pre); pre = e; } if (ans == int.MaxValue) ans = 0; Console.WriteLine(ans); } }} |
Javascript
// Initialize parent array to store the parent of each // component of the graphconst parent = [];for (let i = 0; i < 100010; i++) { parent[i] = i;}// Array used to apply DSU by size in order// to fasten the DSU functionsconst sizez = [];for (let i = 0; i < 100010; i++) { sizez[i] = 1;}// Frequency array to optimize finding the // frequency of component sizes in the graphconst freq = [];for (let i = 0; i < 100010; i++) { freq[i] = 0;}// Set to store different sizes of the componentsconst st = new Set();// This function initializes the DSU // data structurefunction make(i) { parent[i] = i; sizez[i] = 1; freq[1] += 1;}// This function finds the parent of each // component in the graph using path compressionfunction find(v) { if (v === parent[v]) { return v; } parent[v] = find(parent[v]); return parent[v];}// This function is used to Merge two components// together it also updates our frequency array// and set with new sizes and removes older sizesfunction Union(a, b) { a = find(a); b = find(b); if (a !== b) { if (sizez[a] < sizez[b]) { a = b; } // Decrease the frequency of older size freq[sizez[a]] -= 1; // Remove the older size if frequency reaches 0 if (freq[sizez[a]] === 0) { st.delete(sizez[a]); } // Decrease the frequency of older size freq[sizez[b]] -= 1; // Remove the older size if frequency reaches 0 if (freq[sizez[b]] === 0) { st.delete(sizez[b]); } parent[b] = a; sizez[a] += sizez[b]; // Increment the frequency of new size freq[sizez[a]] += 1; // Insert the new size into the set if (freq[sizez[a]] === 1) { st.add(sizez[a]); } }}// Driver Codeconst N = 4;const Q = 2;const queries = [[1, 2], [2, 4]];// Initial component size is 1st.add(1);// Initialize our DSUfor (let i = 1; i <= N; i++) { make(i);}for (let i = 0; i < Q; i++) { const [u, v] = queries[i]; Union(u, v); let ans = Infinity; let pre = -Infinity; // Finding the minimum difference between // adjacent elements of the sorted set for (const e of st.values()) { // If any element has frequency greater // than 1, the answer will be 0 if (freq[e] > 1) { ans = 0; break; } ans = Math.min(ans, e - pre); pre = e; } if (ans === Infinity) { ans = 0; } console.log(ans);} |
Output
0 2
Time Complexity: O(Q * Sqrt(N)), where Q is the number of queries and N is the total number of nodes.
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!
Share your thoughts in the comments
