Queries to find number of connected grid components of given sizes in a Matrix | C ++ implementation for the above approach ; stores information about which cell are already visited in a particular BFS ; Stores the count of cells in the largest connected component ; Function checks if a cell is valid , i . e . it is inside the grid and equal to 1 ; Map to count the frequency of each connected component ; function to calculate the largest connected component ; Iterate over every cell ; Stores the indices of the matrix cells ; Mark the starting cell as visited and push it into the queue ; Iterate while the queue is not empty ; Go to the adjacent cells ; Drivers Code ; Given input array of 1 s and 0 s ; queries array ; sizeof queries array ; Count the frequency of each connected component ; Iterate over the given queries array and And answer the queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int n = 6 ; const int m = 6 ; const int dx [ ] = { 0 , 1 , -1 , 0 } ; const int dy [ ] = { 1 , 0 , 0 , -1 } ; int visited [ n ] [ m ] ; int COUNT ; bool is_valid ( int x , int y , int matrix [ n ] [ m ] ) { if ( x < n && y < m && x >= 0 && y >= 0 ) { if ( visited [ x ] [ y ] == false && matrix [ x ] [ y ] == 1 ) return true ; else return false ; } else return false ; } map < int , int > mp ; void findComponentSize ( int matrix [ n ] [ m ] ) { for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( ! visited [ i ] [ j ] && matrix [ i ] [ j ] == 1 ) { COUNT = 0 ; queue < pair < int , int > > q ; q . push ( { i , j } ) ; visited [ i ] [ j ] = true ; while ( ! q . empty ( ) ) { pair < int , int > p = q . front ( ) ; q . pop ( ) ; int x = p . first , y = p . second ; COUNT ++ ; for ( int i = 0 ; i < 4 ; i ++ ) { int newX = x + dx [ i ] ; int newY = y + dy [ i ] ; if ( is_valid ( newX , newY , matrix ) ) { q . push ( { newX , newY } ) ; visited [ newX ] [ newY ] = true ; } } } mp [ COUNT ] ++ ; } } } } int main ( ) { int matrix [ n ] [ m ] = { { 1 , 1 , 1 , 1 , 1 , 1 } , { 1 , 1 , 0 , 0 , 0 , 0 } , { 0 , 0 , 0 , 1 , 1 , 1 } , { 0 , 0 , 0 , 1 , 1 , 1 } , { 0 , 0 , 1 , 0 , 0 , 0 } , { 1 , 0 , 0 , 0 , 0 , 0 } } ; int queries [ ] = { 6 , 1 , 8 , 2 } ; int N = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; memset ( visited , false , sizeof visited ) ; findComponentSize ( matrix ) ; for ( int i = 0 ; i < N ; i ++ ) cout << mp [ queries [ i ] ] << " ▁ " ; return 0 ; }