# C++ easy O(~n)-time O(~1)-space solution with explanations

• Overview:

The function returns true if and only if:

1. There should be exactly n-1 edges.

2. Edges should connect all nodes together.

In order to check the second statement, we adapt the union-find set to connect two different connected components (See https://en.wikipedia.org/wiki/Disjoint-set_data_structure for explanation.)

Details of the union-find approach:

For each connected components, we use an arbitrary node within the component to represent it. And we use a vector `parents` to record which component each node belongs to, and use an integer `component_num` to record the number of component.

In the beginning, there are n components. So we use the `itoa` function to initialize `parents` to `0, 1, ... , n-1`.

For each edge, we try to determine whether the two nodes of the edge are in the same connected components. If the answer is yes, we find a loop, since the edge is connecting nodes within the same component. Otherwise, we connect the two components into one.

Complexities:

Let alpha(n) denote the inverse function of Ackermann function A(x,x)=n, which grows extremely slow, can be viewed as constant. (https://en.wikipedia.org/wiki/Ackermann_function)

Time complexity: O(n*alpha(n))

Space complexity: O(alpha(n)),

C++:

``````class Solution {
public:
bool validTree(int n, vector<pair<int, int>>& edges) {
// Step 1: Check the number of edges
if (edges.size() != n - 1) {
return false;
}

// Step 2: Union-find set
vector<int> parents(n);
iota(parents.begin(), parents.end(), 0);
for (pair<int, int> edge : edges) {
int root1 = find(parents, edge.first);
int root2 = find(parents, edge.second);
if (root1 == root2) {
return false;
}
else {
parents[root1] = root2;
}
}
return true;
}
private:
// standard function of union-find set
int find(vector<int> &parents, int c) {
if (parents[c] != c) {
parents[c] = find(parents, parents[c]);
}
return parents[c];
}
};``````

• how come space is O(1):

``````    // Step 2: Union-find set
vector<int> parents(n);``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.