[LintCode][Tree] Graph Valid Tree

Problem

More Discussions

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.

Solution

问题的本质就是判断图中有没有环，并且所有的点都联通。
那么我们可以用DFS来遍历所有的点，同时做一些判断

1. 给每个点设颜色：0:未遍历过 1:遍历过一次 2:遍历过2次。那么很容易的可以知道如果有一个点遍历过2次，那肯定存在环。如果DFS之后有一个点从未遍历过，那这个点就在另一个图中，所以也无法构成数。
2. 另外在判断当前点的下面的遍历节点时，我们要出去它的父亲节点，这样可以避免一条边被重复遍历。

class Solution {
private:
    vector<vector<int>> nodes;
    vector<int> nodeColor;
    
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) {
        if (n == 0) {
            return true;
        }
        nodes.resize(n);
        nodeColor.resize(n);
        for(int i = 0; i < edges.size(); i++) {
            int node1 = edges[i][0];
            int node2 = edges[i][1];
            nodes[node1].push_back(node2);
            nodes[node2].push_back(node1);
        }
        for(int i = 0; i < nodeColor.size(); i++) {
            nodeColor[i] = 0;
        }
        bool result = check(0, -1);
        if (!result) {
            return false;
        }
        
        for(int i = 0; i < n; i++) {
            if (nodeColor[i] == 0) {
                return false;
            }
        }
        
        return true;
    }
    
    bool check(int index, int parentIndex) {
        nodeColor[index]++;
        if (nodeColor[index] == 2) {
            return false;
        }
        
        for(int i = 0; i < nodes[index].size(); i++) {
            if (nodes[index][i] != parentIndex) {
                bool result = check(nodes[index][i], index);
                if (!result) {
                    return false;
                }
            }
        }
        
        return true;
    }
};