Graph Valid Tree

Graph Valid Tree

Description:

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 edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

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.

分析：

如果要组成一棵树，要满足下面两个条件：

  1. 连通图。可以通过并查集来判断是否是一个连通图。
  2. 没有回路。通过边数 = 节点数 - 1 && 没有节点链接到自己来完成判断。

这道题，想通了就简单，想不通就不知道如何入手，个人感觉最主要的是边数和节点数的关系。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    bool validTree(int n, vector<vector<int>>& edges) {
        // Write your code here
        if (n - 1 != edges.size()) return false;
        
        int rootCount = 0;
        vector<int> t(n, 0);
        vector<int> pre(n, 0);
        for (int i = 1; i < n; i++) pre[i] = i;
        
        for (int i = 0; i < edges.size(); i++) {
            //if node connect to itself or not.
            if (edges[i][0] == edges[i][1]) return false;
            
            unionOp(pre, edges[i][0], edges[i][1]);
        }
        
        for(int i = 0; i < n; i++) {  
            t[findOp(pre, i)] = 1;
        }
        for(int i = 0; i < n; i++) {
            if (t[i]) rootCount++;
        }
        if (rootCount > 1) return false;
        
        return true;
    }
    
    int findOp(vector<int> &pre, int x) {
        int r = x;
        while(r != pre[r]) r = pre[r];
        
        int i = x, j;
        while(pre[i] != r) {
            j = pre[i];
            pre[i] = r;
            i = j;
        }
        return r;
    }
    
    void unionOp(vector<int> &pre, int x, int y) {
        int fx = findOp(pre, x), fy = findOp(pre, y);
        
        if(fx != fy) {
            pre[fy] = fx;
        }
    }
};