Problem: spooky_splits (2023 round3)

Mrs. Puff is taking her class trick-or-treating! Her \(N\) students, numbered from \(1\) to \(N\), are dressed up in spooky outfits and ready to collect some candy. To divide and conquer every house in Bikini Bottom, she would like to break up the class into equal-sized groups.

\(M\) pairs of students have similar-themed costumes that amplify their spookiness, the \(i\)th being students \(A_i\) and \(B_i\). Ms. Puff's would like to know: for which values of \(K\) can the class be divided into \(K\) groups of equal size without splitting up any of these pairs?

# Constraints

\(1 \leq T \leq 75\)
\(2 \leq N \leq 100\)
\(0 \leq M \leq \frac{N(N-1)}{2}\)
\(1 \leq A_i, B_i \leq N\)
\(A_i \neq B_i\)

Each unordered pair of employees occurs at most once in a given test case.


# Input Format

Input begins with an integer \(T\), the number of test cases. Each case begins with a line containing the two integers \(N\) and \(M\). Then, \(M\) lines follow, the \(i\)th of which contains the two integers \(A_i\) and \(B_i\).


# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by all possible values of \(K\) in ascending order, separated by spaces.


# Sample Explanation

In the first sample case, there are three possible values of \(K\). Here's a possible arrangement:
- \(K = 1\): All students can be put into a single group.
- \(K = 2\): Groups \(\{1, 2, 4, 5, 6, 7\}\) and \(\{3, 8, 9, 10, 11, 12\}\).
- \(K = 3\): Groups \(\{1, 2, 4, 6\}\), \(\{3, 5, 8, 12\}\) and \(\{7, 9, 10, 11\}\).

In the second case, either all students can be in a single group, or each should form a separate group.

In the third test case, the valid values of \(K\), with an example of each, are:
- \(K = 1\): All students can be put into a single group.
- \(K = 2\): Groups \(\{1, 2, 5, 7\}\) and \(\{3, 4, 6, 8\}\).
- \(K = 4\): Groups \(\{1, 7\}\), \(\{2, 5\}\), \(\{3, 6\}\) and \(\{4, 8\}\).


Sample input:
3
12 7
1 2
2 4
4 6
3 8
8 12
9 10
10 11
3 0
8 4
1 7
2 5
6 3
8 4


Sample output:
Case #1: 1 2 3
Case #2: 1 3
Case #3: 1 2 4


Solution: If we draw an edge for each \((A_i, B_i)\), we'll get a graph of the \(N\) students. It's clear that to avoid splitting up any of the \(M\) pairs, we have to avoid splitting up any connected component in the graph. From here, we see that what only the component sizes matter, which can be found with a simple breadth- or depth-first search.

Fixing \(K\), the problem reduces to checking whether the array of component sizes can be partitioned into \(K\) subsets of equal sum. First, if \(N\) is not a multiple of \(K\), then we cannot partition \(N\) into equal-sized groups of size \(N / K\). Otherwise, we'll need to find a valid partition.

Consider a backtracking algorithm that attempts to recursively assign each component to one of the \(K\) groups. We will maintain a size \(K\) array of current group sizes, and only assign to a group if the new size doesn't exceed the target size of \(N / K\). Clearly, this naive method is exponential, and will not be fast enough as we have up to \(100\) components/groups.


One optimization is to observe that for a current state (array of partially-assigned group sizes), e.g. \([1, 1, 1, 2, 0, 3]\), adding to any one of identical groups is the same, so we only have to recurse for one of them. Instead of an array, we can think of the state as a *multiset* of numbers with sum not exceeding \(N\). We can maintain a set of multisets to track states we've already seen and avoid recomputing them. Each group can take on sizes \(0...\frac{N}{K}\) (i.e. \(\frac{N}{K} - 1\) different values). The number of states is the number of ways to choose \(\frac{N}{K} + 1\) elements to fill \(K\) slots with repetition allowed. This is \((\frac{N}{K} + 1)\) [multichoose](https://mathworld.wolfram.com/Multichoose.html) \(K\), equal to \(\bigl( \binom{N/K + 1}{K} \bigr) = \binom{N/K + K}{K} \). At worst, this comes out to \(\approx185{,}000\) states when \(\frac{N}{K}=K=10\).

The overall time complexity will be bounded by the number of \(K\)s to check (a.k.a the number of divisors of \(N\), here at most \(12\) for \(N = 60 \le 100\)) multiplied by the number of states, multiplied by the time to process each state. In practice, the jury's solution solves the full dataset in under a few seconds on a modest system.


Code: #include <iostream>
#include <set>
#include <vector>
using namespace std;

int N, M;
vector<vector<int>> adj;
vector<bool> visit;
vector<int> sizes;

void rec(int u) {
  sizes.back()++;
  visit[u] = true;
  for (int v : adj[u]) {
    if (!visit[v]) {
      rec(v);
    }
  }
}

int tgt;
vector<int> groups;
multiset<int> state;
set<multiset<int>> seen;

bool can_partition(int i) {
  if (i == (int)sizes.size()) {
    for (int sz : groups) {
      if (sz != tgt) {
        return false;
      }
    }
    return true;
  }
  if (seen.count(state)) {
    return false;
  }
  seen.insert(state);
  for (int &g : groups) {
    if (g + sizes[i] <= tgt) {
      state.erase(state.find(g));
      g += sizes[i];
      state.insert(g);
      if (can_partition(i + 1)) {
        return true;
      }
      state.erase(state.find(g));
      g -= sizes[i];
      state.insert(g);
    }
  }
  return false;
}

void solve() {
  cin >> N >> M;
  adj.assign(N, {});
  visit.assign(N, false);
  sizes.clear();
  for (int i = 0, a, b; i < M; i++) {
    cin >> a >> b;
    a--;
    b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for (int i = 0; i < N; i++) {
    if (!visit[i]) {
      sizes.push_back(0);
      rec(i);
    }
  }
  for (int K = 1; K <= N; K++) {
    if (N % K == 0) {
      tgt = N / K;
      groups.assign(K, 0);
      state.clear();
      for (int i = 0; i < K; i++) {
        state.insert(0);
      }
      seen.clear();
      if (can_partition(0)) {
        cout << " " << K;
      }
    }
  }
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ":";
    solve();
    cout << endl;
  }
  return 0;
}