Find first undeleted integer from K to N in given unconnected Graph after performing Q queries | Java 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
class GFG { public static int Get ( int [ ] graph , int a ) { return graph [ a ] = ( graph [ a ] == a ? a : Get ( graph , graph [ a ] ) ) ; } public static void Union ( int [ ] graph , int a , int b ) { a = Get ( graph , a ) ; b = Get ( graph , b ) ; graph [ a ] = b ; } public static void Queries ( int [ ] [ ] queries , int N , int M ) { int [ ] graph = new int [ N + 2 ] ; for ( int i = 1 ; i <= N + 1 ; i ++ ) { graph [ i ] = i ; } for ( int [ ] query : queries ) { if ( query [ 0 ] == 1 ) { Union ( graph , query [ 1 ] , query [ 1 ] + 1 ) ; } else { int a = Get ( graph , query [ 1 ] ) ; if ( a == N + 1 ) System . out . print ( - 1 ) ; else System . out . print ( graph [ a ] + " ▁ " ) ; } } } public static void main ( String args [ ] ) { int N = 5 ; int [ ] [ ] queries = { { 2 , 1 } , { 1 , 1 } , { 2 , 1 } , { 2 , 3 } } ; int Q = queries . length ; Queries ( queries , N , Q ) ; } }