C# DFS Solution


#1
class Solution 
{
    public void Traverse(List<List<int>> grid, bool[][] visited, int i, int j)
    {
        //If the indexes are out of range, we do not process them.
        if(i < 0 || i >= visited.Length || j < 0 || j >= visited[0].Length)
        {
            return;
        }
        
        
        if(!visited[i][j] && grid[i][j] == 1)
        {
            visited[i][j] = true;
        
            Traverse(grid, visited, i, j + 1); //Traverse right horizontally
            Traverse(grid, visited, i, j - 1); //Traverse left horizontally
            Traverse(grid, visited, i - 1, j); //Traverse up vertically
            Traverse(grid, visited, i + 1, j); //Traverse down vertically
        }
        
        
        
        
    }
    
    public int solve(List<List<int>> A) 
    {
        //a boolean array to mark the visited cells so we don't revisit them.
        bool[][] visited = new bool[A.Count][];
        
        for(int i = 0; i < visited.Length; i++)
        {
            visited[i] = new bool[A[0].Count];
        }
        
        int numberOfConnectedComponents = 0;
        
        for(int i = 0; i < A.Count; i++)
        {
            for(int j = 0; j < A[i].Count; j++)
            {
                if(!visited[i][j] && A[i][j] == 1)
                {
                    Traverse(A, visited, i, j);
                    numberOfConnectedComponents++;
                }
            }
        }
        
        return numberOfConnectedComponents;
    }
}