警告：
- 注意区分【强连通分量】，【边双联通分量】，【点双连通分量】。
思考：
-
之前没有做到过边双连通分量的拆解；
-
一个边双联通分量可以看作一个基环上不断加一条链；
-
注意，这里加的链首尾可以为同一个位置。
到这步代码就好弄了。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=14,M=1<<N,INF=1e9;
int n,m,U,a[N][N];
int f[N][M][N],g[M],h[N][M];
struct zj{
int S,u,v;
}t[M];
void chkmin(int &x,int y,zj &a,zj b){
if(x>y)x=y,a=b;
}
int ans[N][N];
void findf(int s,int S,int u){
if(s==u)return;
int v=f[s][S][u];
ans[u][v]=1;
findf(s,S^(1<<u),v);
}
void findh(int s,int S){
int u=h[s][S];
findf(s,S,u);
ans[u][s]=1;
}
void findg(int S){
int Q=t[S].S,u=t[S].u,v=t[S].v;
if(!~v)findh(u,S);
else if(u^v)findf(u,Q,v),findg(S^Q^(1<<u)^(1<<v));
else findh(u,Q),findg(S^Q^(1<<u));
}
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>m,U=(1<<n)-1;
for(int u,v;m--;){
cin>>u>>v,u--,v--;
a[u][v]=a[v][u]=1;
}
memset(f,-1,sizeof f),memset(h,-1,sizeof h);
memset(t,-1,sizeof t);
for(int s=0;s<n;s++){
f[s][1<<s][s]=1;
for(int S=0;S<=U;S++){
for(int u=0;u<n;u++)if(S>>u&1){
if(!~f[s][S][u])continue;
for(int v=0;v<n;v++)if(~S>>v&1){
if(a[u][v])f[s][S|(1<<v)][v]=u;
}
if(a[u][s]&&__builtin_popcount(S)>2)h[s][S]=u;
}
}
}
memset(g,0x3f,sizeof g);
for(int S=0;S<=U;S++){
for(int u=0;u<n;u++)if(S>>u&1){
if(~h[u][S]){
g[S]=__builtin_popcount(S),t[S].u=u;
}
}
}
for(int S=0;S<=U;S++){
for(int T=S;T;--T&=S){
int P=S^T,delta=__builtin_popcount(T)+1;
if(g[P]>INF)continue;
for(int u=0;u<n;u++)if(P>>u&1){
for(int v=u;v<n;v++)if(P>>v&1){
if(u^v){
int Q=T|(1<<u)|(1<<v);
if(!~f[u][Q][v])continue;
chkmin(g[S],g[P]+delta,t[S],{Q,u,v});
}else{
int Q=T|(1<<u);
if(!~h[u][Q])continue;
chkmin(g[S],g[P]+delta,t[S],{Q,u,v});
}
}
}
}
}
cout<<g[U]<<endl;
findg(U);
for(int u=0;u<n;u++){
for(int v=0;v<n;v++){
if(ans[u][v]){
printf("%d %d\n",u+1,v+1);
}
}
}
return 0;
}