# Leetcode: Graph Valid Tree && 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 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.```

This problem can be solved by using union find, reference this blog:https://segmentfault.com/a/1190000003791051

### 思路

1. 这些边是否构成环路，如果有环则不能构成树
2. 这些边是否能将所有节点连通，如果有不能连通的节点则不能构成树

• `union` 将两个节点放入一个集合中
• `find` 找到该节点所属的集合编号
• `areConnected` 判断两个节点是否是一个集合
• `count` 返回该并查集中有多少个独立的集合

### 注意

``` 1 public class Solution {
2     public boolean validTree(int n, int[][] edges) {
3         unionfind uf = new unionfind(n);
4         for (int i=0; i<edges.length; i++) {
5             if (uf.areConnected(edges[i][0], edges[i][1])) return false;
6             else {
7                 uf.union(edges[i][0], edges[i][1]);
8             }
9         }
10         return uf.count()==1;
11     }
12
13     public class unionfind {
14         int[] ids;  //union id for each node
15         int cnt; //the number of independent union
16
17         public unionfind(int size) {
18             this.ids = new int[size];
19             for (int i=0; i<size; i++) {
20                 ids[i] = i;
21             }
22             this.cnt = size;
23         }
24
25         public boolean union(int i, int j) {
26             int src = find(i);
27             int dst = find(j);
28             if (src != dst) {
29                 for (int k=0; k<ids.length; k++) {
30                     if (ids[k] == src) {
31                         ids[k] = dst;
32                     }
33                 }
34                 cnt--;
35                 return true;
36             }
37             return false;
38         }
39
40         public int find(int i) {
41             return ids[i];
42         }
43
44         public boolean areConnected(int i, int j) {
45             return find(i)==find(j);
46         }
47
48         public int count() {
49             return cnt;
50         }
51     }
52 }```

Summary:

Dectect cycle in directed graph:

Detect cycle in a directed graph is using a DFS. Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. In the following graph, there are 3 back edges, marked with cross sign. We can observe that these 3 back edges indicate 3 cycles present in the graph.

To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is back edge. We have used recStack[] array to keep track of vertices in the recursion stack.

Detect cycle in undirected graph:

method 1: Union Find  The time complexity of the union-find algorithm is O(ELogV).

method 2: DFS + parent node  Like directed graphs, we can use DFSto detect cycle in an undirected graph in O(V+E) time. We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle. The assumption of this approach is that there are no parallel edges between any two vertices.

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

## Detect Cycle In Directed/Undirected Graph

Detect Cycle in a Directed Graph https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ 有向图里的环必须是 a->b b->c c->a 类似这种的环(包括自环). 这学期刚上过算法,dfs遍历图会得到dfs tree(如果不是连通图就是forest),并提到了back edge的概念.如果dfs遍历图的时候,有back edge产生,那就说明一定有环. 写起来就按照标准的dfs写,需要一个visit

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