×

# COPR16B : Editorial

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

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.

6★likecs
3.7k2481
accept rate: 9%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,658
×593
×32
×1

question asked: 26 Mar '16, 02:14

question was seen: 554 times

last updated: 29 Mar '16, 16:17