首页 > 代码库 > [LintCode] Graph Valid Tree
[LintCode] Graph Valid Tree
http://www.lintcode.com/en/problem/graph-valid-tree/
DFS 解法:
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) { // Write your code here if (n <= 0 || edges == null || n - 1 != edges.length) { return false; } int[][] matrix = new int[n][n]; Set<Integer> set = new HashSet<Integer>(); for (int i = 0; i < edges.length; i++) { matrix[edges[i][0]][edges[i][1]] = 1; matrix[edges[i][1]][edges[i][0]] = 1; } dfs(matrix, 0, set); return set.size() == n; } private void dfs(int[][] matrix, int start, Set<Integer> set) { if (set.contains(start)) { return; } set.add(start); for (int i = 0; i < matrix.length; i++) { if (matrix[start][i] == 1) { dfs(matrix, i, set); } } } }
Union Find 解法:
public class Solution { /** * @param n an integer * @param edges a list of undirected edges * @return true if it‘s a valid tree, or false */ class UnionFind { int[] id; int[] weight; public UnionFind(int n) { id = new int[n]; weight = new int[n]; for (int i = 0; i < n; i++) { id[i] = i; weight[i] = 1; } } public void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (weight[rootI] < weight[rootJ]) { id[rootI] = rootJ; weight[rootJ] += weight[rootI]; } else { id[rootJ] = rootI; weight[rootI] += weight[rootJ]; } } public int find(int i) { if (id[i] != i) { return find(id[i]); } return i; } } public boolean validTree(int n, int[][] edges) { if (n <= 0 || edges == null || n - 1 != edges.length) { return false; } UnionFind uf = new UnionFind(n); for (int i = 0; i < edges.length; i++) { if (uf.find(edges[i][0]) == uf.find(edges[i][1])) { return false; } uf.union(edges[i][0], edges[i][1]); } return true; } }
这道题还可以用 BFS 解。
[LintCode] Graph Valid Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。