Codeforces 907E(状压DP)

Codeforces 907E
题意：给一个连通有向图，每次选出一个点，这个点所连的所有点就可以成为一个团(完全图，即每两个顶点直接有一条边)，求最少选几个点使得整个图成为一个团，输出方案。

题目数据范围提示是状压DP或者搜索。这里明显是状压DP。
设$dp(S)$为当前团的节点状态，$st_i$为这个点连通点的状态，则
$$dp(S|st_i)=min(dp(s)+1)$$
输出方案，如果当前DP更新了，就把前驱记录，然后最后输出即可。

如果原图已经是团，则直接输出0

知识点：
数据范围小：状压、暴力DFS
团=完全图，即每两个顶点直接有一条边

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, m, st[30], dp[(1 << 22) + 10], pre1[(1 << 22) + 10], pre2[(1 << 22) + 10];
inline void ins(int x, int y) {
    st[x] += (1 << (y - 1)), st[y] += (1 << (x - 1));
}
void clean() {
    ms(st, 0);
    for (int S = 0; S <= (1 << n); S++) dp[S] = 100000000, pre1[S] = pre2[S] = 0;
}
int solve() {
    clean();
    for (int u, v, i = 1; i <= m; i++) scanf("%d%d", &u, &v), ins(u, v);
    for (int i = 1; i <= n; i++) st[i] += (1 << (i - 1));
    int fl = 0;
    for (int i = 1; i <= n; i++) {
        if (st[i] != (1 << n) - 1) fl = 1;
        dp[st[i]] = 1, pre1[st[i]] = i;
    }
    if (!fl) return printf("0\n");
    for (int S = 0; S < (1 << n); S++) {
        for (int i = 1; i <= n; i++) if (S & (1 << (i - 1))) {
            if (dp[S] + 1 < dp[S | st[i]]) {
                dp[S | st[i]] = dp[S] + 1;
                pre1[S | st[i]] = i, pre2[S | st[i]] = S;
            }
        }
    }
    printf("%d\n", dp[(1 << n) - 1]);
    for (int S = (1 << n) - 1; S; S = pre2[S]) printf("%d ", pre1[S]);
    return 0; 
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}