Queries to check if vertices X and Y are in the same Connected Component of an Undirected Graph | C ++ Program to implement the above approach ; Maximum number of nodes or vertices that can be present in the graph ; Store the parent of each vertex ; Stores the size of each set ; Function to initialize the parent of each vertices ; Function to find the representative of the set which contain element v ; Path compression technique to optimize the time complexity ; 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 ; Finding the set representative of each element ; Check if they have different set repersentative ; Compare the set sizes ; Assign parent of smaller set to the larger one ; Add the size of smaller set to the larger one ; Function to check the vertices are on the same set or not ; Check if they have same set representative or not ; Driver Code ; Connected vertices and taking them into single set ; Number of queries ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX_NODES  100005 NEW_LINE int parent [ MAX_NODES ] ; int size_set [ MAX_NODES ] ; void make_set ( int v ) { parent [ v ] = v ; size_set [ v ] = 1 ; } int find_set ( int v ) { if ( v == parent [ v ] ) return v ; return parent [ v ] = find_set ( parent [ v ] ) ; } void union_set ( int a , int b ) { a = find_set ( a ) ; b = find_set ( b ) ; if ( a != b ) { if ( size_set [ a ] < size_set [ b ] ) swap ( a , b ) ; parent [ b ] = a ; size_set [ a ] += size_set [ b ] ; } } string check ( int a , int b ) { a = find_set ( a ) ; b = find_set ( b ) ; return ( a == b ) ? " Yes " : " No " ; } int main ( ) { int n = 5 , m = 3 ; make_set ( 1 ) ; make_set ( 2 ) ; make_set ( 3 ) ; make_set ( 4 ) ; make_set ( 5 ) ; union_set ( 1 , 3 ) ; union_set ( 3 , 4 ) ; union_set ( 3 , 5 ) ; int q = 3 ; cout << check ( 1 , 5 ) << endl ; cout << check ( 3 , 2 ) << endl ; cout << check ( 5 , 2 ) << endl ; return 0 ; }