# Largest connected component on a grid - GeeksforGeeks (2023)

C++ Java Python3 C# Videos

Given a grid with different colors in a different cell, each color represented by a different number. The task is to find out the largest connected component on the grid. Largest component grid refers to a maximum set of cells such that you can move from any cell to any other cell in this set by only moving between side-adjacent cells from the set.

Examples:

Input :

Grid of different colors

Output : 9

Largest connected component of grid

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach :

The approach is to visualize the given grid as a graph with each cell representing a separate node of the graph and each node connected to four other nodes which are to immediately up, down, left, and right of that grid. Now doing a BFS search for every node of the graph, find all the nodes connected to the current node with same color value as the current node.

Here is the graph for above example :

Graph representation of grid

.
At every cell (i, j), a BFS can be done. The possible moves from a cell will be either to right, left, top or bottom. Move to only those cells which are in range and are of the same color. It the same nodes have been visited previously, then the largest component value of the grid is stored in result[][] array. Using memoization, reduce the number of BFS on any cell. visited[][] array is used to mark if the cell has been visited previously and count stores the count of the connected component when a BFS is done for every cell. Store the maximum of the count and print the resultant grid using result[][] array.

Below is the illustration of the above approach:

## C++

`// CPP program to print the largest`

`// connected component in a grid`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`const` `int` `n = 6;`

`const` `int` `m = 8;`

`// stores information about which cell`

`// are already visited in a particular BFS`

`int` `visited[n][m];`

`// result stores the final result grid`

`int` `result[n][m];`

`// stores the count of cells in the largest`

`// connected component`

`int` `COUNT;`

`// Function checks if a cell is valid i.e it`

`// is inside the grid and equal to the key`

`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``;`

`}`

`// BFS to find all cells in`

`// connection with key = input[i][j]`

`void` `BFS(``int` `x, ``int` `y, ``int` `i, ``int` `j, ``int` `input[n][m])`

`{`

`// terminating case for BFS`

`if` `(x != y)`

`return``;`

`visited[i][j] = 1;`

`COUNT++;`

`// x_move and y_move arrays`

`// are the possible movements`

`// in x or y direction`

`int` `x_move[] = { 0, 0, 1, -1 };`

`int` `y_move[] = { 1, -1, 0, 0 };`

`// checks all four points connected with input[i][j]`

`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);`

`}`

`// called every time before a BFS`

`// so that visited array is reset to zero`

`void` `reset_visited()`

`{`

`for` `(``int` `i = 0; i < n; i++)`

`for` `(``int` `j = 0; j < m; j++)`

`visited[i][j] = 0;`

`}`

`// If a larger connected component`

`// is found this function is called`

`// to store information about that component.`

`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;`

`}`

`}`

`}`

`// function to print the result`

`void` `print_result(``int` `res)`

`{`

`cout << ``"The largest connected "`

`<< ``"component of the grid is :"` `<< res << ``"\n"``;`

`// prints the largest component`

`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 << ``"\n"``;`

`}`

`}`

`// function to calculate the largest connected`

`// component`

`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;`

`// checking cell to the right`

`if` `(j + 1 < m)`

`BFS(input[i][j], input[i][j + 1], i, j, input);`

`// updating result`

`if` `(COUNT >= current_max) {`

`current_max = COUNT;`

`reset_result(input[i][j], input);`

`}`

`reset_visited();`

`COUNT = 0;`

(Video) Size of largest Connected components | DFS Application

`// checking cell downwards`

`if` `(i + 1 < n)`

`BFS(input[i][j], input[i + 1][j], i, j, input);`

`// updating result`

`if` `(COUNT >= current_max) {`

`current_max = COUNT;`

`reset_result(input[i][j], input);`

`}`

`}`

`}`

`print_result(current_max);`

`}`

`// Drivers Code`

`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 } };`

`// function to compute the largest`

`// connected component in the grid`

`computeLargestConnectedGrid(input);`

`return` `0;`

`}`

## Java

`// Java program to print the largest`

`// connected component in a grid`

`import` `java.util.*;`

`import` `java.lang.*;`

`import` `java.io.*;`

`class` `GFG`

`{`

`static` `final` `int` `n = ``6``;`

`static` `final` `int` `m = ``8``;`

`// stores information about which cell`

`// are already visited in a particular BFS`

`static` `final` `int` `visited[][] = ``new` `int` `[n][m];`

`// result stores the final result grid`

`static` `final` `int` `result[][] = ``new` `int` `[n][m];`

`// stores the count of`

`// cells in the largest`

`// connected component`

`static` `int` `COUNT;`

`// Function checks if a cell`

`// is valid i.e it is inside`

`// the grid and equal to the key`

`static` `boolean` `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``;`

`}`

`// BFS to find all cells in`

`// connection with key = input[i][j]`

`static` `void` `BFS(``int` `x, ``int` `y, ``int` `i,`

`int` `j, ``int` `input[][])`

`{`

`// terminating case for BFS`

`if` `(x != y)`

`return``;`

`visited[i][j] = ``1``;`

`COUNT++;`

`// x_move and y_move arrays`

`// are the possible movements`

`// in x or y direction`

`int` `x_move[] = { ``0``, ``0``, ``1``, -``1` `};`

`int` `y_move[] = { ``1``, -``1``, ``0``, ``0` `};`

`// checks all four points`

`// connected with input[i][j]`

`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);`

`}`

`// called every time before`

`// a BFS so that visited`

`// array is reset to zero`

`static` `void` `reset_visited()`

`{`

`for` `(``int` `i = ``0``; i < n; i++)`

`for` `(``int` `j = ``0``; j < m; j++)`

`visited[i][j] = ``0``;`

`}`

`// If a larger connected component`

`// is found this function is`

`// called to store information`

`// about that component.`

`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``;`

`}`

`}`

`}`

`// function to print the result`

`static` `void` `print_result(``int` `res)`

`{`

`System.out.println (``"The largest connected "` `+`

`"component of the grid is :"` `+`

`res );`

`// prints the largest component`

(Video) Algorithms: Solve 'Connected Cells' Using DFS

`for` `(``int` `i = ``0``; i < n; i++)`

`{`

`for` `(``int` `j = ``0``; j < m; j++)`

`{`

`if` `(result[i][j] != ``0``)`

`System.out.print(result[i][j] + ``" "``);`

`else`

`System.out.print(``". "``);`

`}`

`System.out.println();`

`}`

`}`

`// function to calculate the`

`// largest connected component`

`static` `void` `computeLargestConnectedGrid(``int` `input[][])`

`{`

`int` `current_max = Integer.MIN_VALUE;`

`for` `(``int` `i = ``0``; i < n; i++)`

`{`

`for` `(``int` `j = ``0``; j < m; j++)`

`{`

`reset_visited();`

`COUNT = ``0``;`

`// checking cell to the right`

`if` `(j + ``1` `< m)`

`BFS(input[i][j], input[i][j + ``1``],`

`i, j, input);`

`// updating result`

`if` `(COUNT >= current_max)`

`{`

`current_max = COUNT;`

`reset_result(input[i][j], input);`

`}`

`reset_visited();`

`COUNT = ``0``;`

`// checking cell downwards`

`if` `(i + ``1` `< n)`

`BFS(input[i][j],`

`input[i + ``1``][j], i, j, input);`

`// updating result`

`if` `(COUNT >= current_max)`

`{`

`current_max = COUNT;`

`reset_result(input[i][j], input);`

`}`

`}`

`}`

`print_result(current_max);`

`}`

`// Driver Code`

`public` `static` `void` `main(String args[])`

`{`

`int` `input[][] = {{``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``}};`

`// function to compute the largest`

`// connected component in the grid`

`computeLargestConnectedGrid(input);`

`}`

`}`

`// This code is contributed by Subhadeep`

## Python3

`# Python3 program to print the largest`

`# connected component in a grid`

`n ``=` `6``;`

`m ``=` `8``;`

`# stores information about which cell`

`# are already visited in a particular BFS`

`visited ``=` `[[``0` `for` `j ``in` `range``(m)]``for` `i ``in` `range``(n)]`

`# result stores the final result grid`

`result ``=` `[[``0` `for` `j ``in` `range``(m)]``for` `i ``in` `range``(n)]`

`# stores the count of cells in the largest`

`# connected component`

`COUNT ``=` `0`

`# Function checks if a cell is valid i.e it`

`# is inside the grid and equal to the key`

`def` `is_valid(x, y, key, ``input``):`

`if` `(x < n ``and` `y < m ``and` `x >``=` `0` `and` `y >``=` `0``):`

`if` `(visited[x][y] ``=``=` `0` `and` `input``[x][y] ``=``=` `key):`

`return` `True``;`

`else``:`

`return` `False``;`

`else``:`

`return` `False``;`

`# BFS to find all cells in`

`# connection with key = input[i][j]`

`def` `BFS(x, y, i, j, ``input``):`

`global` `COUNT`

`# terminating case for BFS`

`if` `(x !``=` `y):`

`return``;`

`visited[i][j] ``=` `1``;`

`COUNT ``+``=` `1`

`# x_move and y_move arrays`

`# are the possible movements`

`# in x or y direction`

`x_move ``=` `[ ``0``, ``0``, ``1``, ``-``1` `]`

`y_move ``=` `[ ``1``, ``-``1``, ``0``, ``0` `]`

`# checks all four points connected with input[i][j]`

`for` `u ``in` `range``(``4``):`

`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``);`

`# called every time before a BFS`

`# so that visited array is reset to zero`

`def` `reset_visited():`

`for` `i ``in` `range``(n):`

`for` `j ``in` `range``(m):`

`visited[i][j] ``=` `0`

`# If a larger connected component`

`# is found this function is called`

`# to store information about that component.`

`def` `reset_result(key, ``input``):`

`for` `i ``in` `range``(n):`

`for` `j ``in` `range``(m):`

`if` `(visited[i][j] !``=` `0` `and` `input``[i][j] ``=``=` `key):`

`result[i][j] ``=` `visited[i][j];`

`else``:`

`result[i][j] ``=` `0``;`

`# function to print the result`

(Video) Connected Components

`def` `print_result(res):`

`print``(``"The largest connected "``+`

`"component of the grid is :"` `+` `str``(res));`

`# prints the largest component`

`for` `i ``in` `range``(n):`

`for` `j ``in` `range``(m):`

`if` `(result[i][j] !``=` `0``):`

`print``(result[i][j], end ``=` `' '``)`

`else``:`

`print``(``'. '``,end ``=` `'')`

`print``()`

`# function to calculate the largest connected`

`# component`

`def` `computeLargestConnectedGrid(``input``):`

`global` `COUNT`

`current_max ``=` `-``10000000000`

`for` `i ``in` `range``(n):`

`for` `j ``in` `range``(m):`

`reset_visited();`

`COUNT ``=` `0``;`

`# checking cell to the right`

`if` `(j ``+` `1` `< m):`

`BFS(``input``[i][j], ``input``[i][j ``+` `1``], i, j, ``input``);`

`# updating result`

`if` `(COUNT >``=` `current_max):`

`current_max ``=` `COUNT;`

`reset_result(``input``[i][j], ``input``);`

`reset_visited();`

`COUNT ``=` `0``;`

`# checking cell downwards`

`if` `(i ``+` `1` `< n):`

`BFS(``input``[i][j], ``input``[i ``+` `1``][j], i, j, ``input``);`

`# updating result`

`if` `(COUNT >``=` `current_max):`

`current_max ``=` `COUNT;`

`reset_result(``input``[i][j], ``input``);`

`print_result(current_max);`

`# Drivers Code`

`if` `__name__``=``=``'__main__'``:`

`input` `=` `[ [ ``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` `] ];`

`# function to compute the largest`

`# connected component in the grid`

`computeLargestConnectedGrid(``input``);`

`# This code is contributed by pratham76`

## C#

`// C# program to print the largest`

`// connected component in a grid`

`using` `System;`

`class` `GFG`

`{`

`public` `const` `int` `n = 6;`

`public` `const` `int` `m = 8;`

`// stores information about which cell`

`// are already visited in a particular BFS`

`public` `static` `readonly` `int``[][] visited =`

`RectangularArrays.ReturnRectangularIntArray(n, m);`

`// result stores the final result grid`

`public` `static` `readonly` `int``[][] result =`

`RectangularArrays.ReturnRectangularIntArray(n, m);`

`// stores the count of cells in the`

`// largest connected component`

`public` `static` `int` `COUNT;`

`// Function checks if a cell is valid i.e`

`// it is inside the grid and equal to the key`

`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``;`

`}`

`}`

`// BFS to find all cells in`

`// connection with key = input[i][j]`

`public` `static` `void` `BFS(``int` `x, ``int` `y, ``int` `i,`

`int` `j, ``int``[][] input)`

`{`

`// terminating case for BFS`

`if` `(x != y)`

`{`

`return``;`

`}`

`visited[i][j] = 1;`

`COUNT++;`

`// x_move and y_move arrays`

`// are the possible movements`

`// in x or y direction`

`int``[] x_move = ``new` `int``[] {0, 0, 1, -1};`

`int``[] y_move = ``new` `int``[] {1, -1, 0, 0};`

`// checks all four points`

`// connected with input[i][j]`

`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);`

`}`

`}`

`}`

`// called every time before`

`// a BFS so that visited`

`// array is reset to zero`

(Video) Grid Connected Solar PV System

`internal` `static` `void` `reset_visited()`

`{`

`for` `(``int` `i = 0; i < n; i++)`

`{`

`for` `(``int` `j = 0; j < m; j++)`

`{`

`visited[i][j] = 0;`

`}`

`}`

`}`

`// If a larger connected component is`

`// found this function is called to`

`// store information about that component.`

`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;`

`}`

`}`

`}`

`}`

`// function to print the result`

`internal` `static` `void` `print_result(``int` `res)`

`{`

`Console.WriteLine(``"The largest connected "` `+`

`"component of the grid is :"` `+ res);`

`// prints the largest component`

`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();`

`}`

`}`

`// function to calculate the`

`// largest connected component`

`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;`

`// checking cell to the right`

`if` `(j + 1 < m)`

`{`

`BFS(input[i][j], input[i][j + 1],`

`i, j, input);`

`}`

`// updating result`

`if` `(COUNT >= current_max)`

`{`

`current_max = COUNT;`

`reset_result(input[i][j], input);`

`}`

`reset_visited();`

`COUNT = 0;`

`// checking cell downwards`

`if` `(i + 1 < n)`

`{`

`BFS(input[i][j], input[i + 1][j],`

`i, j, input);`

`}`

`// updating result`

`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;`

`}`

`}`

`// Driver Code`

`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}`

`};`

`// function to compute the largest`

`// connected component in the grid`

`computeLargestConnectedGrid(input);`

`}`

`}`

`// This code is contributed by Shrikant13`

Output

`The largest connected component of the grid is :9 . . . . . . . . . 1 1 . . . . . . . 1 1 . . . . . . . 1 . . . . . . . 1 1 . . . . . . 1 1 . . . `

My Personal Notes arrow_drop_up

## Videos

1. G-16. Number of Distinct Islands | Constructive Thinking + DFS | C++ | Java
(take U forward)
2. 6.11 Connected Components |How to find Connected Components in Graph | Graph Theory
(Jenny's Lectures CS IT)
3. Applications of Depth First Search | GeeksforGeeks
(GeeksforGeeks)
4. Practice session | Interview Preparation for Graph and Tree | GeeksforGeeks Practice
(GeeksforGeeks Practice)
5. Finding the size of the largest connected component in a graph (2 Solutions!!)
(Roel Van de Paar)
6. Dial’s Algorithm (Optimized Dijkstra for small range weights) | GeeksforGeeks
(GeeksforGeeks)
Top Articles
Latest Posts
Article information

Author: Virgilio Hermann JD

Last Updated: 09/06/2023

Views: 6289

Rating: 4 / 5 (61 voted)

Author information

Name: Virgilio Hermann JD

Birthday: 1997-12-21

Address: 6946 Schoen Cove, Sipesshire, MO 55944

Phone: +3763365785260

Job: Accounting Engineer

Hobby: Web surfing, Rafting, Dowsing, Stand-up comedy, Ghost hunting, Swimming, Amateur radio

Introduction: My name is Virgilio Hermann JD, I am a fine, gifted, beautiful, encouraging, kind, talented, zealous person who loves writing and wants to share my knowledge and understanding with you.