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.
Example 1:
Input:n = 5, andedges = [[0,1], [0,2], [0,3], [1,4]]Output: true
Example 2:
Input:n = 5,andedges = [[0,1], [1,2], [2,3], [1,3], [1,4]]Output: 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.
Related Topics:
Depth-first Search, Breadth-first Search, Union Find, Graph
Similar Questions:
// OJ: https://leetcode.com/problems/graph-valid-tree/
// Author: github.com/lzl124631x
// Time: O(E)
// Space: O(N)
class UnionFind {
private:
vector<int> rank;
vector<int> id;
int count;
int find (int i) {
if (id[i] == i) return i;
return id[i] = find(id[i]);
}
public:
UnionFind(int n) : rank(n, 0), id(n), count(n) {
for (int i = 0; i < n; ++i) id[i] = i;
}
void connect(int i, int j) {
int p = find(i), q = find(j);
if (p == q) return;
if (rank[p] > rank[q]) id[p] = q;
else {
id[q] = p;
if (rank[p] == rank[q]) rank[p]++;
}
--count;
}
int getCount() { return count; }
};
class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
if (edges.size() != n - 1) return false;
UnionFind uf(n);
for (auto &e : edges) uf.connect(e.first, e.second);
return uf.getCount() == 1;
}
};