C# - build graph, DFS iterative and mark visited


  • 0

    build a graph as an array where each node is a list of neighbors. Once the graph is built, just iterate through each node and use it as a starting point to mark off all connections (using DFS). Every starting point that is not yet visited is a new group, increment your group counter.

        public int CountComponents(int n, int[,] edges) 
        {
            List<int>[] graph = new List<int>[n];
            for (int i = 0; i < n; i++) graph[i] = new List<int>();
            for (int i = 0; i < edges.GetLength(0); i++)
            {
                graph[edges[i,0]].Add(edges[i,1]);
                graph[edges[i,1]].Add(edges[i,0]);
            }
            
            bool[] visited = new bool[n];
            int groups = 0;
            Stack<int> stack = new Stack<int>();
            
            for (int i = 0; i < n; i++)
            {
                if (visited[i] == false)
                {
                    // count group
                    groups++;
                    
                    // visit all connected nodes and mark visited - DFS
                    stack.Push(i);
                    while (stack.Count > 0)
                    {
                        int node = stack.Pop();
                        if (visited[node] == true) continue;
                        visited[node] = true;
                        foreach (int neighbor in graph[node]) stack.Push(neighbor);
                    }
                }
            }
            return groups;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.