It looks like you are calling std::set methods find() and erase() in your union_sets function. They are O(log N), moreover, the constant is really huge. Consider getting rid of those calls.

By the way, what you are using looks like union by size, not union by rank.

Your solution is simply not optimal. Before you read any further, I urge you to once again quickly go through your code.

Let's begin. Your logic is correct but its implementation is weak. You are storing the roots (or heads) of each disjoint set in a separate set called 'tmp'. In your Union function, you are making a total of 5 calls on this set 'tmp'. So let's make a rough estimate of the total complexity of your Union function. 2 calls for find_set (to find root) and 5 calls on 'temp' (each O(lg(n)) so it is O(7 * lg(n)). [lg(n) is log n base 2]. With given constraints, total time complexity = O(n * 7 * lg(n) + 2 * n * lg(n)) as you are initialising the set 'tmp' and finally iterating through it at the end to get answer too. When n = 10^5, then complexity = O(9 * 10^5 * lg(10^5)) , which is approximately O(1.5 * 10^7). Add to this the overhead of all these operations and you realize why you get the TLE!! In any decent problem, at most 10^6 (10^7 in rare cases) complexity is required with the most optimal solution (operations can reach 10^8 with the overhead, which is still rare). While on the surface your algorithm looks like O(n * log(n)), it's really not.

So what could you have done better? It's simple really. You need not have to keep the 'tmp' set to store the roots at all. Notice that if a vertex/node 'a' is a root, then parent[a] = a. This way you can identify your root vertex without needing to store it elsewhere. As far as the given problem is concerned, since you are only adding the minimum gold from each disjoint set, you can just store this minimum gold for the whole set in the root vertex itself. That is, gold[a] = min gold from disjoint set where a is the root vertex. The gold[v] value for other vertices which are not root (parent[v] != v) doesn't matter.

I made minimum modifications to your code to show this. It now gets AC.

DSU is one of my favourite topics and I suggest you build a template that you can quickly use. If you are interested, this is my code that I wrote when I saw your question. You can use the template if you wish to. Or you can check out submissions of top coders.

Best of luck!

You should keep things simple, I tried with DSU, here is the link

A=> parent array and other things are simple.

void make_set(int v) {
	parent[v] = v;
	size[v] = 0;
}
 
int get_parent(int v) {
	if (v == parent[v]) {
		return v;
        }
	return parent[v] = get_parent(parent[v]);
}
 
void union_sets(int a, int b) {
	a = get_parent(a);
	b = get_parent(b);
	if (a != b) {
		if (size[a] > size[b]) {
			swap (a, b);
                }
		parent[a] = b;
		size[b] += size[a];
	}
}