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 (k1), 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_i1)=k2}} {(k2)!} \Pi_{i=1}^{k} {\frac{a_{i}^{d_i}}{(d_i1)!}}$ $=(\Pi_{i=1}^{k} {a_i}){(\sum_{i=1}^{k} {a_i})}^{k2}$ (by multinomial expansion theorem). Therefore the number of ways required are $=(\Pi_{i=1}^{k} {a_i}){(\sum_{i=1}^{k} {a_i})}^{k2}$ = ${n}^{k2}(\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}^{k2}$. If k=1, print "Everyone is connected", else print the required answer COMPLEXITYO(n + m), n = number of nodes in graph, m = number of edges in graph AUTHOR'S SOLUTION:Author's solution can be found here. asked 26 Mar '16, 02:14
