题意：给你一张图，问最少保留多少条边，使得这张图是边双联通分量。
思路：如果一个点集中的点已经是边双联通分量，那么从这个点集中的点x出发，经过若干个不是点集中的点，回到点集中的点y（x可能等于y），那么这条路径上的点和原来的点就构成了一个新的边双联通分量。
设dp[i]是状态i中的点构成边双联通分量需要的最少的边数，那么我们需要枚举dp[i]的子集，然后判断剩下的点能不能通过一条链串起来，如果可以，那么就是剩下的链的点的个数 + 1.那么怎么知道有没有链呢？这个也需要处理，设dp2[i][j][k]是从i开始，途中经过了点集k中的点，能不能到j(k中不包括i和j),直接dp处理就可以了。
代码：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define lowbit(x) (x & (-x))
using namespace std;
vector<int> G[14];
int dp[1 << 14], dp2[14][14][1 << 14];
vector<int> re[1 << 14];
pair<int, int> last_pair[1 << 14];
int pre[1 << 14];
int last[14][14][1 << 14];
bool v[1 << 14];
int main() {
int n, m, x, y;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
G[x - 1].push_back(y - 1);
G[y - 1].push_back(x - 1);
}
for (int i = 0; i < n; i++)
v[1 << i] = 1;
memset(dp, 0x3f, sizeof(dp));
dp[1] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < (1 << n); k++) {
dp2[i][j][k] = INF;
}
for (int i = 0; i < n; i++)
for (auto x : G[i]) {
dp2[i][x][0] = 1;
last[i][x][0] = i;
}
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if((i >> j) & 1) continue;
for (int k = 0; k < n; k++) {
if((i >> k) & 1) continue;
if(j == k || dp2[j][k][i] == INF) continue;
for (auto z : G[k]) {
if((i >> z) & 1) continue;
if(z == last[j][k][i]) continue;
int tmp = i ^ (1 << k);
if(dp2[j][z][tmp] == INF) {
dp2[j][z][tmp] = 1;
last[j][z][tmp] = k;
}
}
}
}
}
for (int i = 0; i < n; i++)
dp[1 << i] = 0;
// dp[1] = 0;
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j < n; j++) {
if((i >> j) & 1)
re[i].push_back(j);
}
for (int i = 0; i < (1 << n); i++) {
for (int j = i; j; j = (j - 1) & i) {
int tmp = i ^ j;
int cnt = __builtin_popcount(j) + 1;
if(dp[i] < dp[tmp] + cnt) continue;
for (auto x : re[tmp])
for (auto y : re[tmp]) {
if(dp2[x][y][j] == 1) {
dp[i] = min(dp[i], dp[tmp] + cnt);
last_pair[i] = make_pair(x, y);
pre[i] = tmp;
}
}
}
}
if(dp[(1 << n) - 1] == INF) {
printf("-1
");
} else {
printf("%d
", dp[(1 << n) - 1]);
int now = (1 << n) - 1;
while(!v[now]) {
int x = last_pair[now].first, y = last_pair[now].second;
int tmp = now ^ pre[now];
while(tmp) {
int tmp1 = last[x][y][tmp];
printf("%d %d
", y + 1, tmp1 + 1);
y = tmp1;
tmp ^= (1 << tmp1);
}
printf("%d %d
", x + 1, y + 1);
now = pre[now];
}
}
}