AC C++, UnionFind with path compassion


  • 0
    L
    int countComponents(int n, vector<pair<int, int>>& edges) 
    {
    	int ret = n;
    	vector<pair<int, int>> sets(n);
    	for (int i = 0; i < n; i++)
    	{
    		sets[i].first = i;
    		sets[i].second = 0;
    	}
    
    	function<int(int)> find = [&](int i)
    	{
    		if (sets[i].first != i)
    			sets[i].first = find(sets[i].first);
    
    		return sets[i].first;
    	};
    
    	for (auto &edge : edges)
    	{
    		int x = find(edge.first), y = find(edge.second);
    		if (x != y)
    		{
    			if (sets[x].second > sets[y].second)
    			{
    				sets[y].first = x;
    			}
    			else
    			{
    				sets[x].first = y;
    				if (sets[x].second == sets[y].second)
    				{
    					sets[y].second++;
    				}
    			}
    			n--;
    		}
    	}
    	return n;
    }

Log in to reply
 

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