Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/261.html
You have a graph of n
nodes labeled from 0
to n - 1
. You are given an integer n and a list of edges
where edges[i] = [ai, bi]
indicates that there is an undirected edge between nodes ai
and bi
in the graph.
Return true
if the edges of the given graph make up a valid tree, and false
otherwise.
Example 1:
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true
Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] Output: false
Constraints:
1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= ai, bi < n
ai != bi
- There are no self-loops or repeated edges.
Algorithm
If it is a tree:
- all nodes must be connected, that is, it must be a connected graph
- and there must be no cycles
Use queue to assist the traversal. Here, instead of using a one-dimensional vector to mark whether the node has been visited, a HashSet is used. If a node is traversed and there is no HashSet in the HashSet, the HashSet is added. If it already exists, false is returned.
Code
-
import java.util.*; public class Graph_Valid_Tree { public class Solution { /** * @param n an integer * @param edges a list of undirected edges * @return true if it's a valid tree, or false */ public boolean validTree(int n, int[][] edges) { if (n == 0) { return false; } if (edges.length != n - 1) { // quick check return false; } Map<Integer, Set<Integer>> graph = initializeGraph(n, edges); // bfs Queue<Integer> queue = new LinkedList<>(); Set<Integer> isVisited = new HashSet<>(); queue.offer(0); isVisited.add(0); while (!queue.isEmpty()) { int node = queue.poll(); for (Integer neighbor : graph.get(node)) { if (isVisited.contains(neighbor)) { // cycle found return false; } isVisited.add(neighbor); queue.offer(neighbor); } } return (isVisited.size() == n); // if all nodes connected } private Map<Integer, Set<Integer>> initializeGraph(int n, int[][] edges) { // node => its neibougher Map<Integer, Set<Integer>> graph = new HashMap<>(); for (int i = 0; i < n; i++) { graph.put(i, new HashSet<Integer>()); } for (int i = 0; i < edges.length; i++) { int u = edges[i][0]; int v = edges[i][1]; graph.get(u).add(v); graph.get(v).add(u); } return graph; } } } ############ class Solution { private int[] p; public boolean validTree(int n, int[][] edges) { p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } for (int[] e : edges) { int a = e[0], b = e[1]; if (find(a) == find(b)) { return false; } p[find(a)] = find(b); --n; } return n == 1; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } }
-
// OJ: https://leetcode.com/problems/graph-valid-tree/ // Time: O(N + E) // Space: O(N) class UnionFind { vector<int> id; int cnt; public: UnionFind(int N) : id(N), cnt(N) { iota(begin(id), end(id), 0); } int find(int x) { return id[x] == x ? x : (id[x] = find(id[x])); } void connect(int a, int b) { id[find(a)] = find(b); --cnt; } bool connected(int a, int b) { return find(a) == find(b); } int getCount() { return cnt; } }; class Solution { public: bool validTree(int n, vector<vector<int>>& E) { UnionFind uf(n); for (auto &e : E) { if (uf.connected(e[0], e[1])) return false; uf.connect(e[0], e[1]); } return uf.getCount() == 1; } };
-
class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] p = list(range(n)) for a, b in edges: if find(a) == find(b): return False p[find(a)] = find(b) n -= 1 return n == 1 ############ class Solution: # @param {int} n an integer # @param {int[][]} edges a list of undirected edges # @return {boolean} true if it's a valid tree, or false def validTree(self, n, edges): # Write your code here def dfs(root, graph, visited, parent): visited[root] = 1 for nbr in graph.get(root, []): if nbr == parent: continue elif visited[nbr] != 0: return False if not dfs(nbr, graph, visited, root): return False visited[root] = 2 self.nodeVisited += 1 return True visited = [0 for _ in range(n)] graph = {} self.nodeVisited = 0 for edge in edges: start, end = edge[0], edge[1] graph[start] = graph.get(start, []) + [end] graph[end] = graph.get(end, []) + [start] if dfs(0, graph, visited, -1) and self.nodeVisited == n: return True else: return False
-
func validTree(n int, edges [][]int) bool { p := make([]int, n) for i := range p { p[i] = i } var find func(x int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } for _, e := range edges { a, b := e[0], e[1] if find(a) == find(b) { return false } p[find(a)] = find(b) n-- } return n == 1 }
-
/** * @param {number} n * @param {number[][]} edges * @return {boolean} */ var validTree = function (n, edges) { let p = new Array(n); for (let i = 0; i < n; ++i) { p[i] = i; } function find(x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } for (const [a, b] of edges) { if (find(a) == find(b)) { return false; } p[find(a)] = find(b); --n; } return n == 1; };