### PROBLEM LINK

### Panel Members

**Problem Setter:** Sunny Aggarwal

**Problem Tester:** Pushkar Mishra

**Editorialist:** Prateek Gupta

**Contest Admin:** Praveen Dhinwa and Pushkar Mishra

**Russian Translator:** Sergey Kulik

**Mandarin Translator:** Hu Zecong

**Vietnamese Translator:** VNOI Team

**Language Verifier:** Rahul Arora

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

Dynamic Programming, Graph.

### PROBLEM:

Given a complete graph of N nodes, find the number of ways to remove subset of edges such that after removal, there exist K connected components.

### EXPLANATION

A complete graph of N nodes has N_{C2} edges meaning each node is connected to all other nodes in the graph.

**Solution to Subtask 1**

**Approach**

Since N is pretty small here, we can go bit of brute here. We can consider subset of N_{C2} edges and make a graph using those. The resultant graph can then be checked to have exactly K connected components.

**Pseudo Code:**

Lets see how to use Bit Manipulation technique to form the subset of the given complete graph.

```
for ( int i = 0; i < 1<<edges; i++ ) {
subset_graph = {}
for ( int j = 0; j < edges; j++ ) {
if ( i & (1<<j) ) {
subset_graph = subset_graph U edges[j]
}
}
ans += (number of components in subset_graph == K)
}
```

Now, we need to find how to check if the graph formed by subset of edges has K connected components.

```
int components = 0;
void dfs(int curr)
{
vis[curr] = true;
for ( int i = 0; i < g[curr].size(); i++ ) {
int to = g[curr][i];
if ( vis[to] ) continue;
dfs(to);
}
}
for ( i = 0; i < N; i++ ) {
if ( !vis[i] ) {
components++;
dfs(i);
}
}
```

Let M denote N_{C2} i.e the number of edges in a complete graph of N nodes. Then, overall complexity for this subtask is around \mathcal{O}(MN * 2 ^ {M}) which is infact pretty slow for large values of M.

**Solution to subtask 2, 3 & 4**

The solution to this subtask will indeed require breaking down the problem into smaller sub-problems and then combine their results to find out the result of the bigger problem. Let us see the recurrence involved in breaking down the problem into smaller sub parts.

**Approach**

Let C(i,j) denote the number the of ways to choose j vertices from i vertices. Then, the following equations hold true.

C(i,0) = 1

C(i,i) = 1

C(i,j) = C(i-1,j-1) + C(i-1,j)

This can be precomputed in \mathcal{O}(N^{2}) space and time complexity.

Let F(i,j) denote the number of ways to choose a subset of edges from total i_{C2} edges such that the resultant graph of i vertices has exactly j connected components. At any particular state (i,j), we have added i - 1 nodes into the graph, and now, we will go on to add the i^{th} vertex in our graph. So, as i - 1 vertices are being added till now, there can be atmost i - 1 components. Henceforth, i^{th} vertex can be added in any of the component size. If we assume the size of that component as k, then following equation holds true.

F(i,j) = \sum_{k=1}^{i-1} F(i-k,j-1) * F(k,1) * C(i-1,k-1) for all j >= 2

To place the i^{th} vertex in the graph where i - 1 have already been added, we needed to choose any k - 1 vertices from i - 1 vertices.

F(i,1) = 2^{(i*(i-1))/2} - \sum_{j=2}^{j=i} F(i,j)

For details on the implementation, please look at the setter’s and tester’s solution mentioned in the section below. Do not forget to take modulo M while doing calculations.

### COMPLEXITY

Overall complexity for each test case should be \mathcal{O}(KN^{2}) to pass all the subtasks stated in the problem.