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++)
            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
                    // visit all connected nodes and mark visited - DFS
                    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.