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

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.

Link:

https://leetcode.com/problems/graph-valid-tree/description/

解题方法：

BFS：
关键在于如何在bfs中不走重复路径而又能判断有环，因为题目给的条件是无向图，所以在记录给出的图的边的时候，将其一条无向边记录为两条有向边。例如：
[0, 1]记录为0: 1和1: 0
当从0走向1时，将其反向边1->0删除。如果还能走回0，则说明有环。

Union Find:
用数组的方式表示节点的父节点和rank, 进行联合查找算法。
最后还要统计一下parent数组中i = parent[i]的个数，如果大于1个，则不是一颗数，而是森林。

Tips:

Time Complexity：

O(n)

完整代码：

BFS

bool validTree(int n, vector<pair<int, int>>& edges) {
    if(!n)
        return true;
    vector<unordered_set<int>> nodes(n);
    for(auto a: edges) {
        nodes[a.first].insert(a.second);
        nodes[a.second].insert(a.first);
    }
    unordered_set<int> visited;
    queue<int> Q;
    Q.push(0);
    while(!Q.empty()) {
        int curr = Q.front();
        cout<<curr<<endl;
        Q.pop();
        if(visited.find(curr) != visited.end())
            return false;
        for(auto a: nodes[curr]) {
            Q.push(a);
            nodes[a].erase(curr);
        }
        visited.insert(curr);
    }
    return n == visited.size();
}

Union Find

int find(int node, vector<int>& parent) {
    if(parent[node] == node)
        return node;
    return find(parent[node], parent);
}
bool validTree(int n, vector<pair<int, int>>& edges) {
    vector<int> parent;
    for(int i = 0; i < n; i++) {
        parent.push_back(i);
    }
    vector<int> rank(n, 0);
    for(auto a: edges) {
        int i = find(a.first, parent);
        int j = find(a.second, parent);
        if(i == j)
            return false;
        else {
            if(rank[i] > rank[j])
                parent[j] = i;
            else {
                if(rank[i] == rank[j])
                    rank[j]++;
                parent[i] = j;
            }
        }
    }
    int count = 0;
    for(int i = 0; i < parent.size(); i++) {
        if(parent[i] == i)
            count++;
    }
    return count == 1;
}