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

  • 0


    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.


    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)),


    class Solution {
    	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;
    	// 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];

  • 0

    how come space is O(1):

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

Log in to reply

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