Graph Valid Tree

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 132 ms)

Metric	Value
Runtime	132 ms
Memory	30.6 MB
Date	2020-01-29

Solution

public class Solution {
    public bool ValidTree(int n, int[][] edges) {
        bool[] visited = new bool[n];
    Dictionary<int, List<int>> adjList = new Dictionary<int, List<int>>();
    for (int i = 0; i < n; i++)
    {
        adjList.Add(i, new List<int>());
    }
    
    foreach (var edge in edges)
    {
        adjList[edge[0]].Add(edge[1]);
        adjList[edge[1]].Add(edge[0]);
    }
    
    if(hasCycle(adjList, 0, visited, -1))
    {
        return false;
    }
    return visited.Count(x=> x==false) == 0;
}

public bool hasCycle(Dictionary<int, List<int>> adjList, int u, bool[] visited, int parent)
{
    visited[u] = true;
    
    foreach (var v in adjList[u])
    {
        if((visited[v] && parent !=v )|| (!visited[v] && hasCycle(adjList, v, visited, u)))
        return true;
    }
    return false;
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed