Queries to check if vertices X and Y are in the same Connected Component of an Undirected Graph

0 0 8 minutes read

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
  |
  5   
Output: 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
       |
       8   
Output: 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 vertex
int parent[MAX_NODES];
 
// Stores the size of each set
int size_set[MAX_NODES];
 
// Function to initialize the
// parent of each vertices
void make_set(int v)
{
    parent[v] = v;
    size_set[v] = 1;
}
 
// Function to find the representative
// of the set which contain element v
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 one
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])
            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 not
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 Code
int 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 approach
import java.util.*;
class GFG{
 
// Maximum number of nodes or
// vertices that can be present
// in the graph
static final int MAX_NODES = 100005;
 
// Store the parent of each vertex
static int []parent = new int[MAX_NODES];
 
// Stores the size of each set
static int []size_set = new int[MAX_NODES];
 
// Function to initialize the
// parent of each vertices
static void make_set(int v)
{
    parent[v] = v;
    size_set[v] = 1;
}
 
// Function to find the representative
// of the set which contain element v
static 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 one
static 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 not
static 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 Code
public 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 graph
MAX_NODES = 100005
  
# Store the parent of each vertex
parent = [0 for i in range(MAX_NODES)];
  
# Stores the size of each set
size_set = [0 for i in range(MAX_NODES)];
  
# Function to initialize the
# parent of each vertices
def make_set(v):
     
    parent[v] = v;
    size_set[v] = 1;
  
# Function to find the 
# representative of the 
# set which contain element v
def 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 one
def 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 not
def 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 approach
using System;
 
class GFG{
 
// Maximum number of nodes or
// vertices that can be present
// in the graph
static readonly int MAX_NODES = 100005;
 
// Store the parent of each vertex
static int []parent = new int[MAX_NODES];
 
// Stores the size of each set
static int []size_set = new int[MAX_NODES];
 
// Function to initialize the
// parent of each vertices
static void make_set(int v)
{
    parent[v] = v;
    size_set[v] = 1;
}
 
// Function to find the representative
// of the set which contain element v
static 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 one
static 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 not
static 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 Code
public 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 zambiatek!