Número de componentes conectados en una array bidimensional de strings

Dada una array 2-D mat[][], la tarea es contar el número de componentes conectados en la array. Una componente conexa está formada por todos los elementos iguales que comparten algún lado común con al menos otro elemento de la misma componente.
Ejemplos: 
 

Input: mat[][] = {"bbba", 
                                   "baaa"}
Output: 2
The two connected components are:
bbb       
b

AND

  a
aaa

Input: mat[][] = {"aabba", 
                                   "aabba", 
                                   "aaaca"}
Output: 4

Enfoque: por cada celda que no se haya visitado antes de realizar DFS . DFS cubrirá todas las celdas conectadas (arriba, izquierda, derecha y abajo) con el mismo valor. Entonces, la respuesta sería el total de veces que se ejecuta DFS.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define maxRow 500
#define maxCol 500
 
bool visited[maxRow][maxCol] = { 0 };
 
// Function that return true if mat[row][col]
// is valid and hasn't been visited
bool isSafe(string M[], int row, int col, char c,
                                    int n, int l)
{
    // If row and column are valid and element
    // is matched and hasn't been visited then
    // the cell is safe
    return (row >= 0 && row < n)
           && (col >= 0 && col < l)
           && (M[row][col] == c && !visited[row][col]);
}
 
// Function for depth first search
void DFS(string M[], int row, int col, char c,
                                 int n, int l)
{
    // These arrays are used to get row and column
    // numbers of 4 neighbours of a given cell
    int rowNbr[] = { -1, 1, 0, 0 };
    int colNbr[] = { 0, 0, 1, -1 };
 
    // Mark this cell as visited
    visited[row][col] = true;
 
    // Recur for all connected neighbours
    for (int k = 0; k < 4; ++k)
        if (isSafe(M, row + rowNbr[k],
                  col + colNbr[k], c, n, l))
 
            DFS(M, row + rowNbr[k],
                col + colNbr[k], c, n, l);
}
 
// Function to return the number of
// connectewd components in the matrix
int connectedComponents(string M[], int n)
{
    int connectedComp = 0;
    int l = M[0].length();
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < l; j++) {
            if (!visited[i][j]) {
                char c = M[i][j];
                DFS(M, i, j, c, n, l);
                connectedComp++;
            }
        }
    }
 
    return connectedComp;
}
 
// Driver code
int main()
{
    string M[] = {"aabba", "aabba", "aaaca"};
    int n = sizeof(M)/sizeof(M[0]);
 
    cout << connectedComponents(M, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
static final int maxRow = 500;
static final int maxCol = 500;
 
static boolean visited[][] = new boolean[maxRow][maxCol];
 
// Function that return true if mat[row][col]
// is valid and hasn't been visited
static boolean isSafe(String M[], int row, int col,
                                  char c, int n, int l)
{
    // If row and column are valid and element
    // is matched and hasn't been visited then
    // the cell is safe
    return (row >= 0 && row < n) &&
           (col >= 0 && col < l) &&
           (M[row].charAt(col) == c &&
           !visited[row][col]);
}
 
// Function for depth first search
static void DFS(String M[], int row, int col,
                        char c, int n, int l)
{
    // These arrays are used to get row and column
    // numbers of 4 neighbours of a given cell
    int rowNbr[] = {-1, 1, 0, 0};
    int colNbr[] = {0, 0, 1, -1};
 
    // Mark this cell as visited
    visited[row][col] = true;
 
    // Recur for all connected neighbours
    for (int k = 0; k < 4; ++k)
    {
        if (isSafe(M, row + rowNbr[k],
                      col + colNbr[k], c, n, l))
        {
            DFS(M, row + rowNbr[k],
                   col + colNbr[k], c, n, l);
        }
    }
}
 
// Function to return the number of
// connectewd components in the matrix
static int connectedComponents(String M[], int n)
{
    int connectedComp = 0;
    int l = M[0].length();
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < l; j++)
        {
            if (!visited[i][j])
            {
                char c = M[i].charAt(j);
                DFS(M, i, j, c, n, l);
                connectedComp++;
            }
        }
    }
 
    return connectedComp;
}
 
// Driver code
public static void main(String[] args)
{
    String M[] = {"aabba", "aabba", "aaaca"};
    int n = M.length;
    System.out.println(connectedComponents(M, n));
}
}
 
// This code contributed by PrinciRaj1992

# Python3 implementation of the approach
import numpy as np
 
maxRow = 500
maxCol = 500
 
visited = np.zeros((maxCol, maxRow))
 
# Function that return true if mat[row][col]
# is valid and hasn't been visited
def isSafe(M, row, col, c, n, l) :
                                         
    # If row and column are valid and element
    # is matched and hasn't been visited then
    # the cell is safe
    return ((row >= 0 and row < n) and
            (col >= 0 and col < l) and
            (M[row][col] == c and not
             visited[row][col]));
 
# Function for depth first search
def DFS(M, row, col, c, n, l) :
 
    # These arrays are used to get row
    # and column numbers of 4 neighbours
    # of a given cell
    rowNbr = [ -1, 1, 0, 0 ];
    colNbr = [ 0, 0, 1, -1 ];
 
    # Mark this cell as visited
    visited[row][col] = True;
 
    # Recur for all connected neighbours
    for k in range(4) :
        if (isSafe(M, row + rowNbr[k],
                   col + colNbr[k], c, n, l)) :
 
            DFS(M, row + rowNbr[k],
                col + colNbr[k], c, n, l);
 
# Function to return the number of
# connectewd components in the matrix
def connectedComponents(M, n) :
 
    connectedComp = 0;
    l = len(M[0]);
 
    for i in range(n) :
        for j in range(l) :
            if (not visited[i][j]) :
                c = M[i][j];
                DFS(M, i, j, c, n, l);
                connectedComp += 1;
         
    return connectedComp;
 
# Driver code
if __name__ == "__main__" :
 
    M = ["aabba", "aabba", "aaaca"];
    n = len(M)
 
    print(connectedComponents(M, n));
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
 
class GFG
{
     
static readonly int maxRow = 500;
static readonly int maxCol = 500;
 
static bool [,]visited = new bool[maxRow,maxCol];
 
// Function that return true if mat[row,col]
// is valid and hasn't been visited
static bool isSafe(String []M, int row, int col,
                                char c, int n, int l)
{
    // If row and column are valid and element
    // is matched and hasn't been visited then
    // the cell is safe
    return (row >= 0 && row < n) &&
        (col >= 0 && col < l) &&
        (M[row][col] == c &&
        !visited[row,col]);
}
 
// Function for depth first search
static void DFS(String []M, int row, int col,
                        char c, int n, int l)
{
    // These arrays are used to get row and column
    // numbers of 4 neighbours of a given cell
    int []rowNbr = {-1, 1, 0, 0};
    int []colNbr = {0, 0, 1, -1};
 
    // Mark this cell as visited
    visited[row,col] = true;
 
    // Recur for all connected neighbours
    for (int k = 0; k < 4; ++k)
    {
        if (isSafe(M, row + rowNbr[k],
                    col + colNbr[k], c, n, l))
        {
            DFS(M, row + rowNbr[k],
                col + colNbr[k], c, n, l);
        }
    }
}
 
// Function to return the number of
// connectewd components in the matrix
static int connectedComponents(String []M, int n)
{
    int connectedComp = 0;
    int l = M[0].Length;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < l; j++)
        {
            if (!visited[i,j])
            {
                char c = M[i][j];
                DFS(M, i, j, c, n, l);
                connectedComp++;
            }
        }
    }
 
    return connectedComp;
}
 
// Driver code
public static void Main(String[] args)
{
    String []M = {"aabba", "aabba", "aaaca"};
    int n = M.Length;
    Console.WriteLine(connectedComponents(M, n));
}
}
 
// This code contributed by Rajput-Ji

<script>
 
// JavaScript implementation of the approach
 
      var maxRow = 500;
      var maxCol = 500;
 
    var visited =
    Array(maxRow).fill().map(()=>Array(maxCol).fill(false));
 
    // Function that return true if mat[row][col]
    // is valid and hasn't been visited
    function isSafe( M , row , col,  c , n , l) {
        // If row and column are valid and element
        // is matched and hasn't been visited then
        // the cell is safe
        return (row >= 0 && row < n) &&
        (col >= 0 && col < l) && (M[row].charAt(col) == c
        && !visited[row][col]);
    }
 
    // Function for depth first search
    function DFS( M , row , col,  c , n , l) {
        // These arrays are used to get row and column
        // numbers of 4 neighbours of a given cell
        var rowNbr = [ -1, 1, 0, 0 ];
        var colNbr = [ 0, 0, 1, -1 ];
 
        // Mark this cell as visited
        visited[row][col] = true;
 
        // Recur for all connected neighbours
        for (var k = 0; k < 4; ++k) {
            if (isSafe(M, row + rowNbr[k], col +
            colNbr[k], c, n, l))
            {
                DFS(M, row + rowNbr[k], col +
                colNbr[k], c, n, l);
            }
        }
    }
 
    // Function to return the number of
    // connectewd components in the matrix
    function connectedComponents( M , n) {
        var connectedComp = 0;
        var l = M[0].length;
 
        for (var i = 0; i < n; i++) {
            for (j = 0; j < l; j++) {
                if (!visited[i][j]) {
                    var c = M[i].charAt(j);
                    DFS(M, i, j, c, n, l);
                    connectedComp++;
                }
            }
        }
 
        return connectedComp;
    }
 
    // Driver code
     
        var M = [ "aabba", "aabba", "aaaca" ];
        var n = M.length;
        document.write(connectedComponents(M, n));
 
// This code contributed by gauravrajput1
 
</script>

4

Complejidad de tiempo: O (fila * columnas)
Espacio auxiliar: O (fila * columnas)