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


  • 0

    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];
    	}
    };

  • 0
    Q

    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.