UVA 10227 - Forests

http://uva.onlinejudge.org/external/102/10227.html

If a tree falls in the forest, and there's nobody there to hear, does it make a sound?

A forest contains \(N\) trees and \(P\) persons. Each person has an opinion about a set of trees they heard fall. Your task is print the number of different opinions among the \(P\) persons.

Let's first try to get some intuition about the situation that we are dealing with:

As we can see in the previous image person #1 and #3 has the same opinion, they heard tress \(\{2, 3\}\) fall. In the case of person #2 he heard the trees \(\{2, 4\}\) falls, this give us a total of 2 different opinions, \(\{2,3\}\) and \(\{2,4\}\).

The key observation to solve this problem is to notice that the persons are divided into connected components according to the set of trees they heard fall. For the previous example we have two connected components:

Once again we are going to need the Disjoint Sets data structure to solve this problem. Initially each person has his own opinion, for each pair of people we check if they shared the same opinion with somebody else in the group, if they do we used the operation \(union\_set(x,y)\) to merged this two persons into a connected component, otherwise, continue with the next person. Our answer is the number of connected components after all the \(union\_set(x,y)\) operations.

Finally, something important to remember is that for this problem "having no opinion also counts as having an opinion". Which means that persons that do not heard any trees fall, they should be group together also in one group.