/// <summary>
/// Finds the longest connect region per color.
/// </summary>
/// <returns>Returns a pair that has the color and the count of the connected cells</returns>
public static Tuple<int,int> FindLongestConnectedColor()
{
    int[,] graph = {
                        {1, 1, 1, 2,2,3},
                        {1, 1, 1, 2,2,3},
                        {1, 1, 1, 2,2,3}
                    };

    var graphRowsCount = graph.GetLength(0);
    var graphColumnsCount = graph.GetLength(1);

    var visitedCellsPerColor = new Dictionary<int, HashSet<Tuple<int, int>>>();

    // first int represents the color, second int represents the region cells' count
    var longestRegion = new Tuple<int, int>(-1, -1);


    for (int row = 0; row < graphRowsCount; row++)
    {
        for (int column = 0; column < graphColumnsCount; column++)
        {
            var color = graph[row, column];

            if (!visitedCellsPerColor.ContainsKey(color))
            {
                visitedCellsPerColor.Add(color, new HashSet<Tuple<int, int>>());
            }

            if (!visitedCellsPerColor[color].Contains(new Tuple<int, int>(row, column)))
            {
                var length = GetConnectedRegionLength(row, column, graph, visitedCellsPerColor);
                if (longestRegion.Item2 < length)
                {
                    longestRegion = new Tuple<int, int>(color, length);
                }
            }
        }
    }

    return longestRegion;
}

private static int GetConnectedRegionLength(int row, int column, int[,] graph, Dictionary<int, HashSet<Tuple<int, int>>> visited)
{
    var directionRow = new List<int> { -1, +1, 0, 0 };
    var directionColumn = new List<int> { 0, 0, +1, -1 };

    var connectedCellsCount = 0;

    var color = graph[row, column];

    var q1 = new Queue<int>();
    var q2 = new Queue<int>();

    q1.Enqueue(row);
    q2.Enqueue(column);
    visited[color].Add(new Tuple<int, int>(row, column));
    connectedCellsCount++;

    while (q1.Any())
    {
        // current Row
        var cr = q1.Dequeue();
        // Current Column
        var cc = q2.Dequeue();

        for (int a = 0; a < directionRow.Count; a++)
        {
            var newRow = cr + directionRow[a];
            var newColumn = cc + directionColumn[a];

            if (newRow < 0 || newColumn < 0) continue;
            if (newRow >= graph.GetLength(0) || newColumn >= graph.GetLength(1)) continue;
            if (graph[newRow, newColumn] != color) continue;
            if (visited[color].Contains(new Tuple<int, int>(newRow, newColumn))) continue;

            q1.Enqueue(newRow);
            q2.Enqueue(newColumn);
            visited[color].Add(new Tuple<int, int>(newRow, newColumn));
            connectedCellsCount++;
        }
    }

    return connectedCellsCount;
}