261. Graph Valid Tree

This problem asks whether a given graph represented by edges forms a valid tree. A valid tree is a connected, acyclic graph. This means:

1. Connectivity: Every node is reachable from every other node.
2. Acyclicity: There are no cycles (loops) in the graph.

Two primary approaches effectively solve this: Union-Find and Depth-First Search (DFS).

Solution 1: Union-Find

This approach leverages the Union-Find data structure to efficiently check for cycles and connectivity.

Algorithm:

1. Initialization: Create a parent array p of size n (number of nodes), where p[i] = i initially. This represents each node as its own disjoint set.
2. Iterate through Edges: For each edge [a, b]:
   • Find the root parent of a (find(a)) and b (find(b)).
   • If find(a) == find(b), a cycle is detected (both nodes belong to the same set), so return false.
   • Otherwise, union the sets by setting p[find(a)] = find(b), effectively merging the sets.
   • Decrement n (the number of connected components) because a merge has occurred.
3. Connectivity Check: After processing all edges, if n == 1, all nodes are connected, and there are no cycles, thus it's a valid tree; otherwise, return false.

Time Complexity: O(n*α(n)), where α(n) is the inverse Ackermann function, which is practically a constant. Union-Find operations (find and union) have amortized time complexity of almost O(1). Space Complexity: O(n) to store the parent array.

Code (Python):

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
 
        p = list(range(n))
        for a, b in edges:
            pa, pb = find(a), find(b)
            if pa == pb:
                return False
            p[pa] = pb
            n -= 1
        return n == 1

Other languages (Java, C++, Go, Javascript) follow a similar structure; only syntax varies.

Solution 2: Depth-First Search (DFS)

This approach uses DFS to traverse the graph and detect cycles.

Algorithm:

1. Edge Count Check: If the number of edges isn't n - 1, it cannot be a tree, so return false.
2. Adjacency List: Create an adjacency list g representing the graph.
3. DFS Traversal: Perform a DFS traversal starting from node 0.
   • Use a vis set to track visited nodes.
   • During the DFS, if a visited node is encountered, a cycle is detected, and false is returned.
4. Connectivity Check: If after DFS, the number of visited nodes in vis is equal to n, it means all nodes were reachable, and there were no cycles, signifying a valid tree; otherwise return false.

Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. DFS visits each node and edge once. Space Complexity: O(n) to store the adjacency list and the vis set.

Code (Python):

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        def dfs(i: int):
            vis.add(i)
            for j in g[i]:
                if j not in vis:
                    dfs(j)
 
        if len(edges) != n - 1:
            return False
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = set()
        dfs(0)
        return len(vis) == n
 

Again, other languages would have similar code with syntactic differences. Both Union-Find and DFS offer efficient solutions for this problem. Union-Find usually has a slight edge in performance due to its near-constant-time operations. However, DFS is also quite efficient and might be considered more intuitive for some.