LeetCode Graph Valid Tree

原题链接在这里:https://leetcode.com/problems/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 whether these edges make up a valid tree.

For 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.

题解:

Union-Find, 与Number of Islands II相似.

若是数先判断 边的数量是不是 n-1.

然后判断有没有环,若是find(edge[0],edge[1])返回true 说明edge[0], edge[1]两个点之前就连在一起了.

Time Complexity: O(n*logn). Space: O(n).

AC Java:

 1 public class Solution {
 2     int [] parent;
 3     int [] size;
 4
 5     public boolean validTree(int n, int[][] edges) {
 6         if(n < 0 || edges == null || edges.length != n-1){
 7             return false;
 8         }
 9         parent = new int[n];
10         size = new int[n];
11         for(int i = 0; i<n ;i++){
12             parent[i] = i;
13             size[i] = 1;
14         }
15
16         for(int [] edge : edges){
17             if(!find(edge[0], edge[1])){
18                 union(edge[0], edge[1]);
19             }else{
20                 return false;
21             }
22         }
23         return true;
24     }
25
26     private boolean find(int i, int j){
27         return root(i) == root(j);
28     }
29     private int root(int i){
30         while(i != parent[i]){
31             parent[i] = parent[parent[i]];
32             i = parent[i];
33         }
34         return i;
35     }
36     private void union(int p, int q){
37         int i = root(p);
38         int j = root(q);
39         if(size[i] < size[j]){
40             parent[i] = j;
41             size[j] += size[i];
42         }else{
43             parent[j] = i;
44             size[i] += size[j];
45         }
46     }
47 }
时间: 03-02

LeetCode Graph Valid Tree的相关文章

Leetcode: Graph Valid Tree &amp;&amp; Summary: Detect cycle in directed graph and undirected graph

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. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

[LeetCode#261] Graph Valid Tree

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. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], r

Graph Valid Tree -- LeetCode

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. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

[Swift]LeetCode261.图验证树 $ 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 whether these edges make up a valid tree. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

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 whether these edges make up a valid tree. Notice You can assume that no duplicate edges will appear in edges. Since all edg

[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) {

leetcode 261-Graph Valid Tree(medium)(BFS, DFS, Union find)

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. 这道题主要就是判断1.是否有环路 2. 是否是连通图 可以用DFS, BFS 和 Union find,union find最合适. 对于DFS和BFS,首先都是建立

261. Graph Valid Tree

也是卡了好多天的题目 主要就是介绍了union-find的算法,用于检查Undirected graph有没有环 http://www.geeksforgeeks.org/union-find/ 1 public boolean validTree(int n, int[][] edges) { 2 int[] parent = new int[n]; 3 Arrays.fill(parent, -1); 4 for(int i = 0; i < edges.length ; i++) { 5

leetcode -day29 Binary Tree Inorder Traversal &amp; Restore IP Addresses

1.  Binary Tree Inorder Traversal Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively? 分析:求二叉树的中序