1class Solution {
2    public boolean validTree(int n, int[][] edges) {
3        // Quick check: tree must have exactly n-1 edges
4        if (edges.length != n - 1) {
5            return false;
6        }
7
8        // Build adjacency list
9        List<List<Integer>> graph = new ArrayList<>();
10        for (int i = 0; i < n; i++) {
11            graph.add(new ArrayList<>());
12        }
13        for (int[] edge : edges) {
14            graph.get(edge[0]).add(edge[1]);
15            graph.get(edge[1]).add(edge[0]);
16        }
17
18        // DFS to check for cycles and connectivity
19        boolean[] visited = new boolean[n];
20        if (!dfs(0, -1, graph, visited)) {
21            return false; // Cycle detected
22        }
23
24        // Check if all nodes were visited (connected)
25        for (boolean v : visited) {
26            if (!v) return false;
27        }
28
29        return true;
30    }
31
32    private boolean dfs(int node, int parent, List<List<Integer>> graph, boolean[] visited) {
33        visited[node] = true;
34
35        for (int neighbor : graph.get(node)) {
36            if (!visited[neighbor]) {
37                if (!dfs(neighbor, node, graph, visited)) {
38                    return false;
39                }
40            } else if (neighbor != parent) {
41                // Found cycle: visited node that's not parent
42                return false;
43            }
44        }
45
46        return true;
47    }
48}
49
50/**
51 * Solution using Union-Find (Disjoint Set Union)
52 */
53class SolutionUnionFind {
54    public boolean validTree(int n, int[][] edges) {
55        // Tree must have exactly n-1 edges
56        if (edges.length != n - 1) {
57            return false;
58        }
59
60        UnionFind uf = new UnionFind(n);
61
62        for (int[] edge : edges) {
63            if (!uf.union(edge[0], edge[1])) {
64                return false; // Cycle detected
65            }
66        }
67
68        return true; // No cycles and correct edge count means valid tree
69    }
70
71    class UnionFind {
72        private int[] parent;
73        private int[] rank;
74
75        public UnionFind(int size) {
76            parent = new int[size];
77            rank = new int[size];
78            for (int i = 0; i < size; i++) {
79                parent[i] = i;
80                rank[i] = 1;
81            }
82        }
83
84        public int find(int x) {
85            if (parent[x] != x) {
86                parent[x] = find(parent[x]); // Path compression
87            }
88            return parent[x];
89        }
90
91        public boolean union(int x, int y) {
92            int rootX = find(x);
93            int rootY = find(y);
94
95            if (rootX == rootY) {
96                return false; // Already in same component (cycle)
97            }
98
99            // Union by rank
100            if (rank[rootX] < rank[rootY]) {
101                parent[rootX] = rootY;
102            } else if (rank[rootX] > rank[rootY]) {
103                parent[rootY] = rootX;
104            } else {
105                parent[rootY] = rootX;
106                rank[rootX]++;
107            }
108
109            return true;
110        }
111    }
112}
113
114/**
115 * Solution using BFS
116 */
117class SolutionBFS {
118    public boolean validTree(int n, int[][] edges) {
119        if (edges.length != n - 1) {
120            return false;
121        }
122
123        // Build graph
124        List<List<Integer>> graph = new ArrayList<>();
125        for (int i = 0; i < n; i++) {
126            graph.add(new ArrayList<>());
127        }
128        for (int[] edge : edges) {
129            graph.get(edge[0]).add(edge[1]);
130            graph.get(edge[1]).add(edge[0]);
131        }
132
133        // BFS
134        boolean[] visited = new boolean[n];
135        Queue<int[]> queue = new LinkedList<>();
136        queue.offer(new int[]{0, -1}); // [node, parent]
137        visited[0] = true;
138
139        while (!queue.isEmpty()) {
140            int[] curr = queue.poll();
141            int node = curr[0];
142            int parent = curr[1];
143
144            for (int neighbor : graph.get(node)) {
145                if (!visited[neighbor]) {
146                    visited[neighbor] = true;
147                    queue.offer(new int[]{neighbor, node});
148                } else if (neighbor != parent) {
149                    return false; // Cycle
150                }
151            }
152        }
153
154        // Check connectivity
155        for (boolean v : visited) {
156            if (!v) return false;
157        }
158
159        return true;
160    }
161}
162
163/**
164 * Iterative DFS solution
165 */
166class SolutionIterative {
167    public boolean validTree(int n, int[][] edges) {
168        if (edges.length != n - 1) return false;
169
170        List<Set<Integer>> graph = new ArrayList<>();
171        for (int i = 0; i < n; i++) {
172            graph.add(new HashSet<>());
173        }
174        for (int[] edge : edges) {
175            graph.get(edge[0]).add(edge[1]);
176            graph.get(edge[1]).add(edge[0]);
177        }
178
179        Set<Integer> visited = new HashSet<>();
180        Stack<Integer> stack = new Stack<>();
181        stack.push(0);
182
183        while (!stack.isEmpty()) {
184            int node = stack.pop();
185            if (visited.contains(node)) continue;
186            visited.add(node);
187
188            for (int neighbor : graph.get(node)) {
189                graph.get(neighbor).remove(node); // Remove reverse edge
190                stack.push(neighbor);
191            }
192        }
193
194        return visited.size() == n;
195    }
196}
197