Queries to find the count of connected Non | Count of connected cells ; Function to return the representative of the Set to which x belongs ; If x is parent of itself ; x is representative of the Set ; Otherwise ; Path Compression ; Unites the set that includes x and the set that includes y ; Find the representatives ( or the root nodes ) for x an y ; If both are in the same set ; Decrement count ; If x ' s ▁ rank ▁ is ▁ less ▁ than ▁ y ' s rank ; Otherwise ; Then move x under y ( doesn 't matter which one goes where) ; And increment the result tree 's  rank by 1 ; Function to count the number of connected cells in the matrix ; Store result for queries ; Store representative of each element ; Initially , all elements are in their own set ; Stores the rank ( depth ) of each node ; If the grid [ x * m + y ] is already set , store the result ; Set grid [ x * m + y ] to 1 ; Increment count . ; Check for all adjacent cells to do a Union with neighbour 's  set if neighbour is also 1 ; Store result . ; Driver Code
let ctr = 0 ; function find ( parent , x ) { if ( parent [ x ] == x ) return x ; parent [ x ] = find ( parent , parent [ x ] ) ; return parent [ x ] ; } function setUnion ( parent , rank , x , y ) { let parentx = find ( parent , x ) ; let parenty = find ( parent , y ) ; if ( parenty == parentx ) return ; ctr -- ; if ( rank [ parentx ] < rank [ parenty ] ) { parent [ parentx ] = parenty ; } else if ( rank [ parentx ] > rank [ parenty ] ) { parent [ parenty ] = parentx ; } else { parent [ parentx ] = parenty ; rank [ parenty ] ++ ; } } function solve ( n , m , query ) { let result = new Array ( query . length ) ; let parent = new Array ( n * m ) ; for ( let i = 0 ; i < n * m ; i ++ ) parent [ i ] = i ; let rank = new Array ( n * m ) ; let grid = new Array ( n * m ) ; for ( let i = 0 ; i < ( n * m ) ; i ++ ) { rank [ i ] = 0 ; grid [ i ] = false ; } for ( let i = 0 ; i < query . length ; i ++ ) { let x = query [ i ] [ 0 ] ; let y = query [ i ] [ 1 ] ; if ( grid [ m * x + y ] == true ) { result [ i ] = ctr ; continue ; } grid [ m * x + y ] = true ; ctr ++ ; if ( x > 0 && grid [ m * ( x - 1 ) + y ] == true ) setUnion ( parent , rank , m * x + y , m * ( x - 1 ) + y ) ; if ( y > 0 && grid [ m * ( x ) + y - 1 ] == true ) setUnion ( parent , rank , m * x + y , m * ( x ) + y - 1 ) ; if ( x < n - 1 && grid [ m * ( x + 1 ) + y ] == true ) setUnion ( parent , rank , m * x + y , m * ( x + 1 ) + y ) ; if ( y < m - 1 && grid [ m * ( x ) + y + 1 ] == true ) setUnion ( parent , rank , m * x + y , m * ( x ) + y + 1 ) ; result [ i ] = ctr ; } return result ; } let N = 3 , M = 3 , K = 4 ; let query = [ [ 0 , 0 ] , [ 1 , 1 ] , [ 1 , 0 ] , [ 1 , 2 ] ] ; let result = solve ( N , M , query ) ; for ( let i = 0 ; i < K ; i ++ ) document . write ( result [ i ] + " " ) ;