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

• 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>();

if (nodes[edges[r,1]] == null) nodes[edges[r,1]] = new List<int>();
}

// 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;
}
``````

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