Queries to find the count of connected Non | C ++ program to implement the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int ctr = 0 ; int find ( vector < int > & parent , int x ) { if ( parent [ x ] == x ) return x ; parent [ x ] = find ( parent , parent [ x ] ) ; return parent [ x ] ; } void setUnion ( vector < int > & parent , vector < int > & rank , int x , int y ) { int parentx = find ( parent , x ) ; int 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 ] ++ ; } } vector < int > solve ( int n , int m , vector < pair < int , int > > & query ) { vector < int > result ( query . size ( ) ) ; vector < int > parent ( n * m ) ; for ( int i = 0 ; i < n * m ; i ++ ) parent [ i ] = i ; vector < int > rank ( n * m , 1 ) ; vector < bool > grid ( n * m , 0 ) ; for ( int i = 0 ; i < query . size ( ) ; i ++ ) { int x = query [ i ] . first ; int y = query [ i ] . second ; if ( grid [ m * x + y ] == 1 ) { result [ i ] = ctr ; continue ; } grid [ m * x + y ] = 1 ; ctr ++ ; if ( x > 0 and grid [ m * ( x - 1 ) + y ] == 1 ) setUnion ( parent , rank , m * x + y , m * ( x - 1 ) + y ) ; if ( y > 0 and grid [ m * ( x ) + y - 1 ] == 1 ) setUnion ( parent , rank , m * x + y , m * ( x ) + y - 1 ) ; if ( x < n - 1 and grid [ m * ( x + 1 ) + y ] == 1 ) setUnion ( parent , rank , m * x + y , m * ( x + 1 ) + y ) ; if ( y < m - 1 and grid [ m * ( x ) + y + 1 ] == 1 ) setUnion ( parent , rank , m * x + y , m * ( x ) + y + 1 ) ; result [ i ] = ctr ; } return result ; } int main ( ) { int N = 3 , M = 3 , K = 4 ; vector < pair < int , int > > query = { { 0 , 0 } , { 1 , 1 } , { 1 , 0 } , { 1 , 2 } } ; vector < int > result = solve ( N , M , query ) ; for ( int i = 0 ; i < K ; i ++ ) cout << result [ i ] << " ▁ " ; }