hacker rank - depth first search (graph)

hacker rank - depth first search (graph)

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace ConnectedCellGrid
{
    class Program
    {
        public class DfsGraph
        {
            // node class to store the state of each vertex while performing depth-first-search
            public class Node
            {
                public string name { set; get; }
                public bool visited { set; get; }

                public Node()
                {
                    this.name = String.Empty;
                    this.visited = false;
                }
            }

            // the maximum number of nodes this graph can contain
            public int maxNodes;

            // the adjacents lookup table that will help us navigate the graph
            public int[,] adjacents;

            // the vertices that shall be the nodes of our graph
            public List<Node> nodes;

            public DfsGraph(int maxNodes)
            {
                this.maxNodes = maxNodes;
                this.nodes = new List<Node>(maxNodes);
                this.adjacents = new int[maxNodes, maxNodes];

                // intializing all adjacent values as 0
                for (int i = 0; i < maxNodes; i++)
                    for (int j = 0; j < maxNodes; j++)
                        adjacents[i, j] = 0;
            }

            // function Dfs (depth first search): 
            // 1. navigating all graphs starting by a default node
            // 2. each node traversed is pushed into a stack (to know our way back to the original node)
            // 3. at a dead end, we go back, and find the next adjacent node (through the adjacents matrix)
            // 4. finally, we get all graphs and we find the maximum graph by points (number of nodes traversed)
            public void Dfs(int node)
            {
                bool allGraphNavigated = false;
                List<int> graphAreas = new List<int>(); 

                while (!allGraphNavigated)
                {
                    int area = 0;
                    int nextNode = node;
                    Stack<int> visits = new Stack<int>();

                    visits.Push(nextNode);
                    nodes[nextNode].visited = true;
                    area++;

                    while (visits.Count > 0)
                    {
                        nextNode = GetUnVisitedAdjacent(nextNode);

                        //Console.WriteLine("adjacent is: {0}", nextNode);

                        if (nextNode != -1)
                        {
                            area++;
                            visits.Push(nextNode);
                            nodes[nextNode].visited = true;

                            //Console.WriteLine("nextVertex is: {0}", nextNode);
                        }
                        else
                        {
                            //Console.WriteLine("popped is: {0}", visits.Peek());

                            nextNode = visits.Pop();
                        }
                    }

                    graphAreas.Add(area);

                    // we are trying to know if there any unvisited not, so we start a new grap traversing
                    if (nodes.Where(n => !n.visited).Any())
                        node = nodes.IndexOf(nodes.Where(n => !n.visited).First());
                    else
                        allGraphNavigated = true;
                }

                Console.WriteLine(graphAreas.Max());
            }

            // function AddVertex: inserting a new vertex, with the name (index of last vertex + 1)
            public void AddNode(String nodeName)
            {
                nodes.Add(new Node() { name = nodeName });
            }

            // function AddAdjacent: making the connection between two nodes to form an adjacent (node 0 <---> node 1)
            public void AddAdjacent(int node, int adjacent)
            {
                adjacents[node, adjacent] = 1;
                adjacents[adjacent, node] = 1;
            }

            // function AddAdjacent: making the connection between two nodes to form an adjacent by named nodes (node 0 <---> node 1)
            public void AddAdjacent(string node, string adjacent)
            {
                int nodeIndex = nodes.IndexOf(nodes.Where(n => n.name == node).First());
                int adjacentIndex = nodes.IndexOf(nodes.Where(n => n.name == adjacent).First());

                adjacents[nodeIndex, adjacentIndex] = 1;
                adjacents[adjacentIndex, nodeIndex] = 1;
            }

            // function GetUnVisitedAdjacent: looking up the adjacent matrix to find the next adjacent point to "vertex" that hasn't been visited
            private int GetUnVisitedAdjacent(int node)
            {
                if (node >= 0)
                    for (int i = 0; i < maxNodes; i++)
                        if (adjacents[node, i] == 1 && !nodes[i].visited)
                            return i;

                return -1;
            }
        }

        static void Main(string[] args)
        {
            // A depth first search algorith would work fine in the case of this problem. It was challenging because:
            // 1. The "adjacents" were not provided, and I had to extract them (provided as a form of a matrix)
            // 2. I have to calculate all graph paths in order get the biggest region

            int nodes = 0;
            int rows = int.Parse(Console.ReadLine());
            int columns = int.Parse(Console.ReadLine());
            int[,] matrix = new int[rows, columns];

            // getting input and counting the nodes
            for (int i = 0; i < rows; i++)
            {
                int[] values = Console.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();

                for (int j = 0; j < values.Length; j++)
                {
                    nodes++;
                    matrix[i, j] = values[j];
                }
            }

            DfsGraph graph = new DfsGraph(nodes);

            // adding named nodes in order to refer to them later on when adding the adjacents
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < columns; j++)
                    if (matrix[i, j] == 1)
                        graph.AddNode(i + "." + j);

            // extracting the adjacents, which got me into two traps (two fault submissions)
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < columns; j++)
                {
                    if (matrix[i, j] == 1)
                    {
                        if (i + 1 < rows)
                            if (matrix[i + 1, j] == 1)
                                graph.AddAdjacent(i + "." + j, (i + 1) + "." + j);

                        if (j + 1 < columns)
                            if (matrix[i, j + 1] == 1)
                                graph.AddAdjacent(i + "." + j, i + "." + (j + 1));

                        if (i + 1 < rows && j + 1 < columns)
                            if (matrix[i + 1, j + 1] == 1)
                                graph.AddAdjacent(i + "." + j, (i + 1) + "." + (j + 1));

                        if (i + 1 < rows && j - 1 >= 0)
                            if (matrix[i + 1, j - 1] == 1)
                                graph.AddAdjacent(i + "." + j, (i + 1) + "." + (j - 1));
                    }
                }
            }

            // starting the depth first search
            graph.Dfs(0);
        }

    }
}