Largest connected component on a grid | C # 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 ; Driver Code ; function to compute the largest connected component in the grid
using System ; class GFG { public const int n = 6 ; public const int m = 8 ; public static readonly int [ ] [ ] visited = RectangularArrays . ReturnRectangularIntArray ( n , m ) ; public static readonly int [ ] [ ] result = RectangularArrays . ReturnRectangularIntArray ( n , m ) ; public static int COUNT ; internal static bool is_valid ( int x , int y , int key , int [ ] [ ] input ) { if ( x < n && y < m && x >= 0 && y >= 0 ) { if ( visited [ x ] [ y ] == 0 && input [ x ] [ y ] == key ) { return true ; } else { return false ; } } else { return false ; } } public static void BFS ( int x , int y , int i , int j , int [ ] [ ] input ) { if ( x != y ) { return ; } visited [ i ] [ j ] = 1 ; COUNT ++ ; int [ ] x_move = new int [ ] { 0 , 0 , 1 , - 1 } ; int [ ] y_move = new int [ ] { 1 , - 1 , 0 , 0 } ; for ( int u = 0 ; u < 4 ; u ++ ) { if ( ( is_valid ( i + y_move [ u ] , j + x_move [ u ] , x , input ) ) == true ) { BFS ( x , y , i + y_move [ u ] , j + x_move [ u ] , input ) ; } } } internal static void reset_visited ( ) { for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { visited [ i ] [ j ] = 0 ; } } } internal static void reset_result ( int key , int [ ] [ ] input ) { for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( visited [ i ] [ j ] == 1 && input [ i ] [ j ] == key ) { result [ i ] [ j ] = visited [ i ] [ j ] ; } else { result [ i ] [ j ] = 0 ; } } } } internal static void print_result ( int res ) { Console . WriteLine ( " The ▁ largest ▁ connected ▁ " + " component ▁ of ▁ the ▁ grid ▁ is ▁ : " + res ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( result [ i ] [ j ] != 0 ) { Console . Write ( result [ i ] [ j ] + " ▁ " ) ; } else { Console . Write ( " . ▁ " ) ; } } Console . WriteLine ( ) ; } } public static void computeLargestConnectedGrid ( int [ ] [ ] input ) { int current_max = int . MinValue ; 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 ) ; } public static class RectangularArrays { public static int [ ] [ ] ReturnRectangularIntArray ( int size1 , int size2 ) { int [ ] [ ] newArray = new int [ size1 ] [ ] ; for ( int array1 = 0 ; array1 < size1 ; array1 ++ ) { newArray [ array1 ] = new int [ size2 ] ; } return newArray ; } } public static void Main ( string [ ] args ) { int [ ] [ ] input = new int [ ] [ ] { new int [ ] { 1 , 4 , 4 , 4 , 4 , 3 , 3 , 1 } , new int [ ] { 2 , 1 , 1 , 4 , 3 , 3 , 1 , 1 } , new int [ ] { 3 , 2 , 1 , 1 , 2 , 3 , 2 , 1 } , new int [ ] { 3 , 3 , 2 , 1 , 2 , 2 , 2 , 2 } , new int [ ] { 3 , 1 , 3 , 1 , 1 , 4 , 4 , 4 } , new int [ ] { 1 , 1 , 3 , 1 , 1 , 4 , 4 , 4 } } ; computeLargestConnectedGrid ( input ) ; } }