PROBLEM LINK:
Author: Bhuvnesh Jain
Tester: Bhuvnesh Jain
Editorialist: Bhuvnesh Jain
DIFFICULTY:
MEDIUM
PREREQUISITES:
BFS/DFS, Combinatorics, Multinomial Theorem
PROBLEM:
Find the number of ways to connect the k clusters of a graph when k>=2 using minimum number of edges, else print “Everyone is connected”.
EXPLANATION:
First of all the minimum of number of edges to be used is (k-1), where k is the number of components in the graph, which can be found easily using BFS/DFS.
Now, notice that if you consider the k components as vertices, then if you add the k−1 edges to make the graph connected you actually get a tree of k vertices. So every tree on k vertices generates a set of ways to connect the graph. Label the components by 1, 2 \cdots, k and their sizes by a_1,a_2, \cdots, a_k. If T is on the set of vertices {1,2⋯,k}, then the number of ways of connecting an edges (i,j) \in E(T) is n_{i,j} = a_i.a_j.
Thus, the number of ways of connecting the components using T
is \Pi_{(i,j) \in E(T)} n_{i,j} = \Pi_{i=1}^{k} a_{i}^{d_i} where d_i is the degree of vertex i in the tree T.
So, the number of ways of connecting the components is
\sum_{T \ tree \ of \ K_k} \Pi_{i=1}^{k} a_{i}^{d_i} = \sum_{\sum_{i=1}^{n} d_i=2(k−1)} N(d_1,d_2,\cdots,d_k) \Pi_{i=1}^{k} a_{i}^{d_i}, where N(d_1,d_2,\cdots,d_k) is the number of labelled trees on k vertices and labelled vertex i has degree d_i.
We have N(d_1,d_2,\cdots,d_k) = \frac{(k−2)!}{\Pi_{i=1}^{k} (d_i−1)!}.
See here for more info.
So, \sum_{T \ tree \ of \ K_k} \Pi_{i=1}^{k} a_{i}^{d_i} = \sum_{\sum_{i=1}^{n} d_i=2(k−1)} {(k−2)!} {\Pi_{i=1}^{k} \frac{a_{i}^{d_i}}{(d_i−1)!}}
= (\Pi_{i=1}^{k} {a_i}) \sum_{\sum_{i=1}^{n} {(d_i-1)=k-2}} {(k-2)!} \Pi_{i=1}^{k} {\frac{a_{i}^{d_i}}{(d_i-1)!}}
=(\Pi_{i=1}^{k} {a_i}){(\sum_{i=1}^{k} {a_i})}^{k-2} (by multinomial expansion theorem).
Therefore the number of ways required are =(\Pi_{i=1}^{k} {a_i}){(\sum_{i=1}^{k} {a_i})}^{k-2} = {n}^{k-2}(\Pi_{i==1}^{k} {a_i}), since \sum_{i=1}^{k} {a_i} = n, where n = total number of vertices.
Now, to implement the above algorithm, just run bfs on the graph. For each connected component found, find the number of vertices in it and multiply the answer by that number. In the end multiply the final answer by {n}^{k-2}. If k=1, print “Everyone is connected”, else print the required answer
COMPLEXITY
O(n + m), n = number of nodes in graph, m = number of edges in graph
AUTHOR’S SOLUTION:
Author’s solution can be found here.