PROBLEM LINKS
DIFFICULTY
SIMPLE
PREREQUISITES
Graph Theory, Union Find, Depth First Search
PROBLEM
An Office has several people on which a relationship of being mutual friends is defined. Two people who are friends will always choose to accompany each other while escaping from fire.
Under these conditions, what are the maximum number of escape routes may be built such that none of them may be empty.
Also, each set of people who escape together, must have a captain assigned. Count the number of ways of assigning captains.
QUICK EXPLANATION
Let us define a graph whose vertices are people. An undirected edge connects two people who are friends.
On this graph, two vertices will be of the same color if they share an edge. This represents that the two people should have to go in the same fire escape route. We wish to maximize the number of colors used.
All the vertices in a connected component in this graph will have to be in the same color.
The above is easy to see because
- If A and B are friends
- and B and C are friends
- Given that A and B should be the same color
- and B and C should be the same color
- A, B and C, all three should be the same color
This observation leads us to the following
The maximum number of fire escape routes that may be built is equal to the number of connected components.
The second part of the problem - Finding the ways to assign captains - is equal to the product of the number of vertices in each connected component. This can be derived by simple permutation / combination. (Since we need exactly 1 member from each set, the answer must be the product of the cardinality of the sets).
EXPLANATION
The number of connected components can be found by use of either of the following techniques
Depth First Search
Since this is an undirected graph, the number of times a Depth First Search starts from an unvisited vertex is equal to the number of connected components. We would like to store the graph as an adjacency list due to the large number of vertices (the number of edges are not too many).
Lets look at dfs implementation in pseudo-code. Both the Setter’s and Tester’s coe use DFS to solve the problem.
for u = 1 to N
if u is not visited
connected_components++
dfs(u)
dfs(u)
mark_visited(u)
for all children v, of u
if v is not visited
dfs(v)
Union Find
Union Find or Disjoint Set Data structures allow you to merge two sets of items together dynamically and maintain for each item - to which set does it belongs. You can consume a Union Find data structure to join each pair of friends. At the end of this, just count the number of distinct components to get the answer.
for u = 1 to N
initialize-new-set-with-1-item(u)
for e = 1 to M /* all edges */
join-sets( e.first, e.second )
Let cc = Array of size N
for u = 1 to N
cc[ find-set-root(u) ]++
for u = 1 to N
if cc[u] > 0
connected_components++
There is one detail missing from the above two approaches. Handling of part 2 of the question. We wish to find the number of items in each connected component and find the product of these numbers.
- In the dfs approach, maintaining a global “size” and incrementing it can solve the problem
- or return the counts in the return value of dfs
- In the disjoint set approach, as demonstrated in the pseudo-code, the array cc stores the number of items in each connected component at the end
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
