Givennnodes labeled from0ton - 1and a list ofundirectededges (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 areundirected,[0, 1]is the same as[1, 0]and thus will not appear together in edges.
Have you met this question in a real interview?
Yes
Example
Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
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\(edges.size\(\) != n-1\)
return false;
union\_find<int> uf\(n\);
for \(auto edge : edges\) {
if\(uf.compressed\_find\(edge\[0\]\) == uf.compressed\_find\(edge\[1\]\)\)
return false;
uf.union\_op\(edge\[0\], edge\[1\]\);
}
return true;
}
private:
template <typename T>
class union\_find
{
public:
union\_find\(vector<T>& items\) {
for \(auto& item : items\) {
father\[item\] = item;
}
}
union\_find\(int n\) {
for \(int i = 0; i < n; ++i\){
father\[i\] = i;
}
}
T find\(T val\) {
T parent = val;
while \(parent != father\[parent\]\) {
parent = father\[parent\];
}
return parent;
}
T compressed\_find\(T val\) {
T parent = val;
while \(parent != father\[parent\]\) {
parent = father\[parent\];
}
auto fa = val;
while \(fa != father\[fa\]\) {
auto temp = father\[fa\];
father\[fa\] = parent;
fa = temp;
}
return parent;
}
void union\_op\(T a, T b\) {
T fa = compressed\_find\(a\);
T fb = compressed\_find\(b\);
if \(fa != fb\) {
father\[fa\] = fb;
}
}
private:
unordered\_map<T, T> father;
};
};