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
using System ; using System . Collections . Generic ; public class GFG { class pair { public int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int n = 6 ; static int m = 6 ; static int [ ] dx = { 0 , 1 , - 1 , 0 } ; static int [ ] dy = { 1 , 0 , 0 , - 1 } ; static int [ , ] visited = new int [ n , m ] ; static int COUNT ; static bool is_valid ( int x , int y , int [ , ] matrix ) { if ( x < n && y < m && x >= 0 && y >= 0 ) { if ( visited [ x , y ] == 0 && matrix [ x , y ] == 1 ) return true ; else return false ; } else return false ; } static Dictionary < int , int > mp = new Dictionary < int , int > ( ) ; static void findComponentSize ( int [ , ] matrix ) { for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( visited [ i , j ] == 0 && matrix [ i , j ] == 1 ) { COUNT = 0 ; List < pair > q = new List < pair > ( ) ; q . Add ( new pair ( i , j ) ) ; visited [ i , j ] = 1 ; while ( q . Count > 0 ) { pair p = q [ 0 ] ; q . RemoveAt ( ) ; int x = p . first , y = p . second ; COUNT ++ ; for ( int k = 0 ; k < 4 ; k ++ ) { int newX = x + dx [ k ] ; int newY = y + dy [ k ] ; if ( is_valid ( newX , newY , matrix ) ) { q . Add ( new pair ( newX , newY ) ) ; visited [ newX , newY ] = 1 ; } } } if ( mp . ContainsKey ( COUNT ) ) { mp [ COUNT ] += 1 ; } else { mp . Add ( COUNT , 1 ) ; } } } } } public static void Main ( ) { int [ , ] matrix = new int [ , ] { { 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 = queries . Length ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { visited [ i , j ] = 0 ; } } findComponentSize ( matrix ) ; for ( int i = 0 ; i < N ; i ++ ) if ( mp . ContainsKey ( queries [ i ] ) != false ) Console . Write ( mp [ queries [ i ] ] + " ▁ " ) ; } }