资讯专栏INFORMATION COLUMN

[LeetCode] Graph Valid Tree [Union Find]

104828720 / 2733人阅读

Problem

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Example

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Note

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Solution

</>复制代码

  1. public class Solution {
  2. int[] parents;
  3. public boolean validTree(int n, int[][] edges) {
  4. if (n-1 != edges.length) {
  5. return false;
  6. }
  7. parents = new int[n];
  8. //initialize n nodes as each own parent
  9. for (int i = 0; i < n; i++) {
  10. parents[i] = i;
  11. }
  12. for (int i = 0; i < n-1; i++) {
  13. if (find(edges[i][0]) == find(edges[i][1])) {
  14. return false; //if two nodes on edge[i] have the same parent, this edge makes a circle causing it invalid
  15. }
  16. else union(edges[i][0], edges[i][1]); //else union the two nodes on edge[i]
  17. }
  18. return true;
  19. }
  20. public int find(int node) {
  21. //find the very first parent node, which is when the parent is the node itself
  22. if (parents[node] == node) {
  23. return node;
  24. }
  25. //find parent recursively
  26. return find(parents[node]);
  27. }
  28. public void union(int a, int b) {
  29. int finda = parents[a], findb = parent[b];
  30. //when node a and node b have different ancient parents, union them with the same parent
  31. if (finda != findb) {
  32. parents[finda] = findb;
  33. }
  34. }
  35. }
Update 2018-10

</>复制代码

  1. class Solution {
  2. public boolean validTree(int n, int[][] edges) {
  3. if (edges.length != n-1) return false;
  4. int[] nums = new int[n];
  5. Arrays.fill(nums, -1);
  6. for (int i = 0; i < edges.length; i++) {
  7. int x = find(nums, edges[i][0]);
  8. int y = find(nums, edges[i][1]);
  9. if (x == y) return false;
  10. nums[x] = y;
  11. }
  12. return true;
  13. }
  14. private int find(int[] nums, int k) {
  15. if (nums[k] == -1) return k;
  16. else return find(nums, nums[k]);
  17. }
  18. }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/65399.html

相关文章

  • [Leetcode] Graph Valid Tree 图与树

    摘要:这样就将一个集合的节点归属到同一个集合号下了。最后如果并查集中只有一个集合,则说明可以构建树。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check w...

    luqiuwen 评论0 收藏0
  • [Leetcode] Graph Valid Tree 判断一个图是否为树

    摘要:只有一个连通分量还没有环,就是树,无根树。无向图边的两端是对称的,无向图讲究连通这个概念,没有方向,没有拓扑,很像集合,所以非常适合用并查集来解决。并查集写法参考注意方法用找的老大哥,合并的是的老大哥。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each...

    xbynet 评论0 收藏0
  • 261. Graph Valid Tree

    摘要:题目链接检查图的连通性及是否有环,可以,,从一个点出发看能不能遍历所有的点,同时来检查是否有环。还可以用检查是否有环,最后看的数量是否等于来判断是不是。 261. Graph Valid Tree 题目链接:https://leetcode.com/problems... 检查图的连通性及是否有环,可以dfs,bfs,从一个点出发看能不能遍历所有的点,同时visited来检查是否有环。...

    Jinkey 评论0 收藏0
  • [LeetCode] 684. Redundant Connection

    Problem In this problem, a tree is an undirected graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one...

    lncwwn 评论0 收藏0
  • [LeetCode] 399. Evaluate Division

    Problem Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the ...

    BlackMass 评论0 收藏0

发表评论

0条评论

104828720

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<