Find first undeleted integer from K to N in given unconnected Graph after performing Q queries | C ++ program for the above approach ; Function to perform th Get operation of disjoint set union ; Function to perform the union operation of dijoint set union ; Update the graph [ a ] as b ; Function to perform given queries on set of vertices initially not connected ; Stores the vertices ; Mark every vertices rightmost vertex as i ; Traverse the queries array ; Check if it is first type of the givan query ; Get the parent of a ; Print the answer for the second query ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int Get ( vector < int > & graph , int a ) { return graph [ a ] = ( graph [ a ] == a ? a : Get ( graph , graph [ a ] ) ) ; } void Union ( vector < int > & graph , int a , int b ) { a = Get ( graph , a ) ; b = Get ( graph , b ) ; graph [ a ] = b ; } void Queries ( vector < pair < int , int > > & queries , int N , int M ) { vector < int > graph ( N + 2 ) ; for ( int i = 1 ; i <= N + 1 ; i ++ ) { graph [ i ] = i ; } for ( auto query : queries ) { if ( query . first == 1 ) { Union ( graph , query . second , query . second + 1 ) ; } else { int a = Get ( graph , query . second ) ; if ( a == N + 1 ) cout << -1 << " ▁ " ; else cout << graph [ a ] << " ▁ " ; } } } int main ( ) { int N = 5 ; vector < pair < int , int > > queries { { 2 , 1 } , { 1 , 1 } , { 2 , 1 } , { 2 , 3 } } ; int Q = queries . size ( ) ; Queries ( queries , N , Q ) ; return 0 ; }