Queries to find number of connected grid components of given sizes in a Matrix | Java implementation for the above approach ; stores information about which cell are already visited in a particular BFS ; Stores the final result grid ; 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
import java . util . * ; class GFG { static class pair { 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 [ ] [ ] result = new int [ n ] [ m ] ; static int COUNT ; static boolean 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 HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; 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 ; Queue < pair > q = new LinkedList < > ( ) ; q . add ( new pair ( i , j ) ) ; visited [ i ] [ j ] = 1 ; while ( ! q . isEmpty ( ) ) { pair p = q . peek ( ) ; q . remove ( ) ; 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 . put ( COUNT , mp . get ( COUNT ) + 1 ) ; } else { mp . put ( COUNT , 1 ) ; } } } } } public static void main ( String [ ] args ) { int matrix [ ] [ ] = { { 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 ; findComponentSize ( matrix ) ; for ( int i = 0 ; i < N ; i ++ ) System . out . print ( ( mp . get ( queries [ i ] ) != null ? mp . get ( queries [ i ] ) : 0 ) + " ▁ " ) ; } }