abc310D 带限制的分组方案数

将n个人分成T组，有m条限制条件，第i个条件为{a[i],b[i]}，表示a[i]与b[i]不能分到同一组，问总共有多少种可行的分组方案？
1<=T<=n<=10

由于最多只有10人，直接爆搜也能过，可以再加个剪枝：如果剩下人每人单独一组都不够T组则不可行。另外，为了去重，可以按编号从小到大的顺序，依次考虑每个人，要么加到已有的组里，要么自成一组。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
#define rep(i,a,b) for(ll i=a; i<=b; i++)
#define per(i,a,b) for(ll i=b; i>=a; i--)
////////////////////////////////////////////////////
ll n, T, m, ans;
set<ll> g[15];
set<pair<ll,ll>> forbid;
void dfs(ll x, ll t) {
    if (x > n) {
        if (t == T) {
            ans += 1;
        }
        return;
    }
    if (t > T) {
        return;
    }
    if (n-x+1+t < T) {
        return;
    }
    rep(i,1,t) {
        int ok = 1;
        for (auto i : g[i]) {
            ll j = x;
            if (i > j) swap(i, j);
            if (forbid.count({i,j}))
                ok = 0;
        }
        if (ok) {
            g[i].insert(x);
            dfs(x+1, t);
            g[i].erase(x);
        }
    }
    g[t+1].insert(x);
    dfs(x+1, t+1);
    g[t+1].erase(x);
}
void solve() {
    cin >> n >> T >> m;
    rep(i,1,m) {
        ll a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        forbid.insert({a,b});
    }
    dfs(1, 0);
    cout << ans << "\n";
}
////////////////////////////////////////////////////
int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}
int myinit = []() {
    cin.tie(0)->sync_with_stdio(0);
    return 0;
}();