Largest connected component on a grid | CPP program to print the largest connected component in a grid ; stores information about which cell are already visited in a particular BFS ; result 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 the key ; BFS to find all cells in connection with key = input [ i ] [ j ] ; terminating case for BFS ; x_move and y_move arrays are the possible movements in x or y direction ; checks all four points connected with input [ i ] [ j ] ; called every time before a BFS so that visited array is reset to zero ; If a larger connected component is found this function is called to store information about that component . ; function to print the result ; prints the largest component ; function to calculate the largest connected component ; checking cell to the right ; updating result ; checking cell downwards ; updating result ; Drivers Code ; function to compute the largest connected component in the grid
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int n = 6 ; const int m = 8 ; int visited [ n ] [ m ] ; int result [ n ] [ m ] ; int COUNT ; bool is_valid ( int x , int y , int key , int input [ n ] [ m ] ) { if ( x < n && y < m && x >= 0 && y >= 0 ) { if ( visited [ x ] [ y ] == false && input [ x ] [ y ] == key ) return true ; else return false ; } else return false ; } void BFS ( int x , int y , int i , int j , int input [ n ] [ m ] ) { if ( x != y ) return ; visited [ i ] [ j ] = 1 ; COUNT ++ ; int x_move [ ] = { 0 , 0 , 1 , -1 } ; int y_move [ ] = { 1 , -1 , 0 , 0 } ; for ( int u = 0 ; u < 4 ; u ++ ) if ( is_valid ( i + y_move [ u ] , j + x_move [ u ] , x , input ) ) BFS ( x , y , i + y_move [ u ] , j + x_move [ u ] , input ) ; } void reset_visited ( ) { for ( int i = 0 ; i < n ; i ++ ) for ( int j = 0 ; j < m ; j ++ ) visited [ i ] [ j ] = 0 ; } void reset_result ( int key , int input [ n ] [ m ] ) { for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( visited [ i ] [ j ] && input [ i ] [ j ] == key ) result [ i ] [ j ] = visited [ i ] [ j ] ; else result [ i ] [ j ] = 0 ; } } } void print_result ( int res ) { cout << " The ▁ largest ▁ connected ▁ " << " component ▁ of ▁ the ▁ grid ▁ is ▁ : " << res << " STRNEWLINE " ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( result [ i ] [ j ] ) cout << result [ i ] [ j ] << " ▁ " ; else cout << " . ▁ " ; } cout << " STRNEWLINE " ; } } void computeLargestConnectedGrid ( int input [ n ] [ m ] ) { int current_max = INT_MIN ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { reset_visited ( ) ; COUNT = 0 ; if ( j + 1 < m ) BFS ( input [ i ] [ j ] , input [ i ] [ j + 1 ] , i , j , input ) ; if ( COUNT >= current_max ) { current_max = COUNT ; reset_result ( input [ i ] [ j ] , input ) ; } reset_visited ( ) ; COUNT = 0 ; if ( i + 1 < n ) BFS ( input [ i ] [ j ] , input [ i + 1 ] [ j ] , i , j , input ) ; if ( COUNT >= current_max ) { current_max = COUNT ; reset_result ( input [ i ] [ j ] , input ) ; } } } print_result ( current_max ) ; } int main ( ) { int input [ n ] [ m ] = { { 1 , 4 , 4 , 4 , 4 , 3 , 3 , 1 } , { 2 , 1 , 1 , 4 , 3 , 3 , 1 , 1 } , { 3 , 2 , 1 , 1 , 2 , 3 , 2 , 1 } , { 3 , 3 , 2 , 1 , 2 , 2 , 2 , 2 } , { 3 , 1 , 3 , 1 , 1 , 4 , 4 , 4 } , { 1 , 1 , 3 , 1 , 1 , 4 , 4 , 4 } } ; computeLargestConnectedGrid ( input ) ; return 0 ; }