Given an undirected graph consisting of N vertices and M edges and queries Q[][] of the type {X, Y}, the task is to check if the vertices X and Y are in the same connected component of the Graph.
Examples:
Input: Q[][] = {{1, 5}, {3, 2}, {5, 2}}
Graph:
1-3-4 2 | 5Output: Yes No No
Explanation:
From the given graph, it can be observed that the vertices {1, 5} are in the same connected component.
But {3, 2} and {5, 2} are from different components.
Input: Q[][] = {{1, 9}, {2, 8}, {3, 5}, {7, 9}}
Graph:
1-3-4 2-5-6 7-9 | 8Output: No Yes No Yes
Explanation:
From the given graph, it can be observed that the vertices {2, 8} and {7, 9} is from same connected component.
But {1, 9} and {3, 5} are from different components.
Approach: The idea is to use the Disjoint Set-Union to solve the problem. The basic interface of the Disjoint set union data structure used is as follows:
- make_set(v): To create a new set consisting of the new element v.
- find_set(v): Returns the representative of the set that contains the element v. This is optimized using Path Compression.
- union_set(a, b): Merges the two specified sets (the set in which the element is located, and the set in which the element b is located). Two connected vertices are merged to form a single set(Connected Components).
- Initially, all the vertices will be a different set (i.e parent of itself ) and are formed using make_set function.
- The vertices will be merged if two of them are connected using union_set function.
- Now, for each query, use the find_set function to check if the given two vertices are from the same set or not.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Maximum number of nodes or// vertices that can be present// in the graph#define MAX_NODES 100005// Store the parent of each vertexint parent[MAX_NODES];// Stores the size of each setint size_set[MAX_NODES];// Function to initialize the// parent of each verticesvoid make_set(int v){ parent[v] = v; size_set[v] = 1;}// Function to find the representative// of the set which contain element vint find_set(int v){ if (v == parent[v]) return v; // Path compression technique to // optimize the time complexity return parent[v] = find_set(parent[v]);}// Function to merge two different set// into a single set by finding the// representative of each set and merge// the smallest set with the larger onevoid union_set(int a, int b){ // Finding the set representative // of each element a = find_set(a); b = find_set(b); // Check if they have different set // repersentative if (a != b) { // Compare the set sizes if (size_set[a] < size_set[b]) swap(a, b); // Assign parent of smaller set // to the larger one parent[b] = a; // Add the size of smaller set // to the larger one size_set[a] += size_set[b]; }}// Function to check the vertices// are on the same set or notstring check(int a, int b){ a = find_set(a); b = find_set(b); // Check if they have same // set representative or not return (a == b) ? "Yes" : "No";}// Driver Codeint main(){ int n = 5, m = 3; make_set(1); make_set(2); make_set(3); make_set(4); make_set(5); // Connected vertices and taking // them into single set union_set(1, 3); union_set(3, 4); union_set(3, 5); // Number of queries int q = 3; // Function call cout << check(1, 5) << endl; cout << check(3, 2) << endl; cout << check(5, 2) << endl; return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{// Maximum number of nodes or// vertices that can be present// in the graphstatic final int MAX_NODES = 100005;// Store the parent of each vertexstatic int []parent = new int[MAX_NODES];// Stores the size of each setstatic int []size_set = new int[MAX_NODES];// Function to initialize the// parent of each verticesstatic void make_set(int v){ parent[v] = v; size_set[v] = 1;}// Function to find the representative// of the set which contain element vstatic int find_set(int v){ if (v == parent[v]) return v; // Path compression technique to // optimize the time complexity return parent[v] = find_set(parent[v]);}// Function to merge two different set// into a single set by finding the// representative of each set and merge// the smallest set with the larger onestatic void union_set(int a, int b){ // Finding the set representative // of each element a = find_set(a); b = find_set(b); // Check if they have different set // repersentative if (a != b) { // Compare the set sizes if (size_set[a] < size_set[b]) { a = a+b; b = a-b; a = a-b; } // Assign parent of smaller set // to the larger one parent[b] = a; // Add the size of smaller set // to the larger one size_set[a] += size_set[b]; }}// Function to check the vertices// are on the same set or notstatic String check(int a, int b){ a = find_set(a); b = find_set(b); // Check if they have same // set representative or not return (a == b) ? "Yes" : "No";}// Driver Codepublic static void main(String[] args){ int n = 5, m = 3; make_set(1); make_set(2); make_set(3); make_set(4); make_set(5); // Connected vertices and taking // them into single set union_set(1, 3); union_set(3, 4); union_set(3, 5); // Number of queries int q = 3; // Function call System.out.print(check(1, 5) + "\n"); System.out.print(check(3, 2) + "\n"); System.out.print(check(5, 2) + "\n");}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 Program to implement# the above approach# Maximum number of nodes or# vertices that can be present# in the graphMAX_NODES = 100005 # Store the parent of each vertexparent = [0 for i in range(MAX_NODES)]; # Stores the size of each setsize_set = [0 for i in range(MAX_NODES)]; # Function to initialize the# parent of each verticesdef make_set(v): parent[v] = v; size_set[v] = 1; # Function to find the # representative of the # set which contain element vdef find_set(v): if (v == parent[v]): return v; # Path compression technique to # optimize the time complexity parent[v] = find_set(parent[v]); return parent[v] # Function to merge two # different set into a # single set by finding the# representative of each set # and merge the smallest set # with the larger onedef union_set(a, b): # Finding the set # representative # of each element a = find_set(a); b = find_set(b); # Check if they have # different set # repersentative if (a != b): # Compare the set sizes if (size_set[a] < size_set[b]): swap(a, b); # Assign parent of # smaller set to # the larger one parent[b] = a; # Add the size of smaller set # to the larger one size_set[a] += size_set[b]; # Function to check the vertices# are on the same set or notdef check(a, b): a = find_set(a); b = find_set(b); # Check if they have same # set representative or not if a == b: return ("Yes") else: return ("No")# Driver code if __name__=="__main__": n = 5 m = 3; make_set(1); make_set(2); make_set(3); make_set(4); make_set(5); # Connected vertices # and taking them # into single set union_set(1, 3); union_set(3, 4); union_set(3, 5); # Number of queries q = 3; # Function call print(check(1, 5)) print(check(3, 2)) print(check(5, 2))# This code is contributed by rutvik_56 |
C#
// C# program to implement// the above approachusing System;class GFG{// Maximum number of nodes or// vertices that can be present// in the graphstatic readonly int MAX_NODES = 100005;// Store the parent of each vertexstatic int []parent = new int[MAX_NODES];// Stores the size of each setstatic int []size_set = new int[MAX_NODES];// Function to initialize the// parent of each verticesstatic void make_set(int v){ parent[v] = v; size_set[v] = 1;}// Function to find the representative// of the set which contain element vstatic int find_set(int v){ if (v == parent[v]) return v; // Path compression technique to // optimize the time complexity return parent[v] = find_set(parent[v]);}// Function to merge two different set// into a single set by finding the// representative of each set and merge// the smallest set with the larger onestatic void union_set(int a, int b){ // Finding the set representative // of each element a = find_set(a); b = find_set(b); // Check if they have different set // repersentative if (a != b) { // Compare the set sizes if (size_set[a] < size_set[b]) { a = a + b; b = a - b; a = a - b; } // Assign parent of smaller set // to the larger one parent[b] = a; // Add the size of smaller set // to the larger one size_set[a] += size_set[b]; }}// Function to check the vertices// are on the same set or notstatic String check(int a, int b){ a = find_set(a); b = find_set(b); // Check if they have same // set representative or not return (a == b) ? "Yes" : "No";}// Driver Codepublic static void Main(String[] args){ //int n = 5, m = 3; make_set(1); make_set(2); make_set(3); make_set(4); make_set(5); // Connected vertices and taking // them into single set union_set(1, 3); union_set(3, 4); union_set(3, 5); // Number of queries //int q = 3; // Function call Console.Write(check(1, 5) + "\n"); Console.Write(check(3, 2) + "\n"); Console.Write(check(5, 2) + "\n");}}// This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript Program to implement // the above approach // Maximum number of nodes or // vertices that can be present // in the graph let MAX_NODES = 100005; // Store the parent of each vertex let parent = new Array(MAX_NODES); // Stores the size of each set let size_set = new Array(MAX_NODES); // Function to initialize the // parent of each vertices function make_set(v) { parent[v] = v; size_set[v] = 1; } // Function to find the representative // of the set which contain element v function find_set(v) { if (v == parent[v]) return v; // Path compression technique to // optimize the time complexity return parent[v] = find_set(parent[v]); } // Function to merge two different set // into a single set by finding the // representative of each set and merge // the smallest set with the larger one function union_set(a, b) { // Finding the set representative // of each element a = find_set(a); b = find_set(b); // Check if they have different set // repersentative if (a != b) { // Compare the set sizes if (size_set[a] < size_set[b]) { let temp = a; a = b; b = temp; } // Assign parent of smaller set // to the larger one parent[b] = a; // Add the size of smaller set // to the larger one size_set[a] += size_set[b]; } } // Function to check the vertices // are on the same set or not function check(a, b) { a = find_set(a); b = find_set(b); // Check if they have same // set representative or not return (a == b) ? "Yes" : "No"; } let n = 5, m = 3; make_set(1); make_set(2); make_set(3); make_set(4); make_set(5); // Connected vertices and taking // them into single set union_set(1, 3); union_set(3, 4); union_set(3, 5); // Number of queries let q = 3; // Function call document.write(check(1, 5) + "</br>"); document.write(check(3, 2) + "</br>"); document.write(check(5, 2) + "</br>");</script> |
Output:
Yes No No
Time Complexity: O(N + M + sizeof(Q))
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!
