Queries to find number of connected grid components of given sizes in a Matrix | Python 3 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
n = 6 NEW_LINE m = 6 NEW_LINE dx = [ 0 , 1 , - 1 , 0 ] NEW_LINE dy = [ 1 , 0 , 0 , - 1 ] NEW_LINE visited = [ [ False for i in range ( m ) ] for j in range ( n ) ] NEW_LINE result = [ [ 0 for i in range ( m ) ] for j in range ( n ) ] NEW_LINE COUNT = 0 NEW_LINE def is_valid ( x , y , matrix ) : NEW_LINE INDENT if ( x < n and y < m and x >= 0 and y >= 0 ) : NEW_LINE INDENT if ( visited [ x ] [ y ] == False and matrix [ x ] [ y ] == 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT mp = { } NEW_LINE def findComponentSize ( matrix ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT if ( visited [ i ] [ j ] == False and matrix [ i ] [ j ] == 1 ) : NEW_LINE INDENT COUNT = 0 NEW_LINE q = [ ] NEW_LINE q . append ( [ i , j ] ) NEW_LINE visited [ i ] [ j ] = True NEW_LINE while ( len ( q ) != 0 ) : NEW_LINE INDENT p = q [ 0 ] NEW_LINE q = q [ 1 : ] NEW_LINE x = p [ 0 ] NEW_LINE y = p [ 1 ] NEW_LINE COUNT += 1 NEW_LINE for i in range ( 4 ) : NEW_LINE INDENT newX = x + dx [ i ] NEW_LINE newY = y + dy [ i ] NEW_LINE if ( is_valid ( newX , newY , matrix ) ) : NEW_LINE INDENT q . append ( [ newX , newY ] ) NEW_LINE visited [ newX ] [ newY ] = True NEW_LINE DEDENT DEDENT DEDENT if COUNT in mp : NEW_LINE INDENT mp [ COUNT ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT mp [ COUNT ] = 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT 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 ] ] NEW_LINE queries = [ 6 , 1 , 8 , 2 ] NEW_LINE N = len ( queries ) NEW_LINE findComponentSize ( matrix ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT if queries [ i ] in mp : NEW_LINE print ( mp [ queries [ i ] ] , end = " ▁ " ) NEW_LINE else : NEW_LINE print ( 0 , end = " ▁ " ) NEW_LINE DEDENT DEDENT