我們可以每遇到一條邊,就把兩個 node union 在一起,然後最後只要 set number 是 1 就好。另外要注意因為是 Tree,所以不能有任何的 cycle,而且每個點都要能走得到,所以 edge 數一定要是 n-1。實作如下:
Copy class Solution {
public :
bool validTree ( int n , vector < vector < int >> & edges) {
if ( edges . size () != n - 1 ) {
return false ;
}
// Init for union find
parent . reserve (n);
for ( int i = 0 ; i < n; i ++ ) {
parent [i] = i;
}
setNumber = n;
// Connect all edges
for ( auto e : edges) {
connect ( e [ 0 ] , e [ 1 ]);
}
return setNumber == 1 ;
}
private :
int setNumber;
vector <int> parent;
void connect ( int nodeA , int nodeB) {
int rootA = find (nodeA);
int rootB = find (nodeB);
if (rootA != rootB) {
parent [rootB] = rootA;
setNumber -- ;
}
}
int find ( int node) {
if (node == parent [node])
return node;
vector <int> path;
while (node != parent [node]) {
path . push_back (node);
node = parent [node];
}
for ( auto n : path) {
parent [n] = node;
}
return node;
}
};
Runtime: 20 ms, faster than 66.35% of C++ online submissions for Graph Valid Tree. Memory Usage: 12 MB, less than 88.89% of C++ online submissions for Graph Valid Tree.