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             int x = find(parent, edges[i][0]);
 6             int y = find(parent, edges[i][1]);
 7             if(x == y) {
 8                 return false;
 9             }
10             parent[x] = y;
11         }
12         return edges.length == n - 1;
13     }
14
15     private int find(int[] parent, int i) {
16         if(parent[i] == -1) {
17             return i;
18         }
19         return find(parent, parent[i]);
20     }
时间: 08-20

261. Graph Valid Tree的相关文章

[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

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

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

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

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,首先都是建立

Leetcode总结之Graph

package Graph; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Prior