C# - DFS cycle search iterative - O(n) time and O(n) space


  • 0

    Here I use an array of lists to form my graph. Iterate edges collection and add the link to each of the nodes for each edge. Then use DFS (iterative with stack) and visited array to detect any cycles. If no cycles are found the last thing to check is if we have enough edges to connect all the nodes.

        public bool ValidTree(int n, int[,] edges) 
        {
            // build graph
            List<int>[] nodes = new List<int>[n];
            for (int r = 0; r < edges.GetLength(0); r++)
            {
                if (nodes[edges[r,0]] == null) nodes[edges[r,0]] = new List<int>();
                nodes[edges[r,0]].Add(edges[r,1]);
                
                if (nodes[edges[r,1]] == null) nodes[edges[r,1]] = new List<int>();
                nodes[edges[r,1]].Add(edges[r,0]);
            }
            
            // check for any cycles
            bool[] visited = new bool[n];
            for (int node = 0; node < n; node++)
            {
                if (!visited[node] && nodes[node] != null)
                {
                    if (HasCycle(nodes, node, visited)) return false;
                }
            }
            
            // no cycles found - require enough nodes to connect all
            return edges.GetLength(0) == n - 1;
        }
        
        // DFS cycle search - iterative
        public bool HasCycle(List<int>[] nodes, int startNode, bool[] visited)
        {
            Stack<int> stack = new Stack<int>();
            stack.Push(-1); // no parent
            stack.Push(startNode);
            
            while (stack.Count > 0)
            {
                int node = stack.Pop();
                int parent = stack.Pop();
                
                // cycle found
                if (visited[node]) return true;
                
                // mark visited
                visited[node] = true;
                
                foreach (int child in nodes[node])
                {
                    if (child != parent)
                    {
                        stack.Push(node);
                        stack.Push(child);
                    }
                }
            }
            
            // no cycles starting at this node
            return false;
        }
    

Log in to reply
 

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