题目描述
求一个图补成边双图的最少加边数。
样例
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
2
算法1
(Tarjan) $O(n)$
$Tarjan$ e-DCC缩点,然后将叶子节点数+1后除2就是答案。
因为我们只要把所有的叶子节点连起来,那么这些节点到其他点就有两种走法(原树上和新加的边上),其他点也是如此。
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
struct edge{
int to,next;
}s[2][20200];
int ls[2],head[2][10010];
void link(int k,int a,int b){
s[k][ls[k]].to=b;
s[k][ls[k]].next=head[k][a];
head[k][a]=ls[k]++;
}
int pre[10010];
int belong[10010];
int getf(int u){
return belong[u];
}
int dfs(int k,int u,int f,int &endx){
int le=0;
endx=u;
pre[u]=f;
for(int i=head[k][u],y,tmp,tmp2;i;i=s[k][i].next)
if((y=s[k][i].to)!=f){
if((tmp=dfs(k,y,u,tmp2))>le){
le=tmp;
endx=tmp2;
}
}
return le+1;
}
int dfn[3010],low[3010],stamp;
int sta[3010],top;
int ins[3010];
int ind[3010];
int pc[3010][3010];
int cnt;
void tarjan(int u,int fa){
dfn[u]=low[u]=++stamp;
sta[++top]=u;ins[u]=1;
int y;
for(int i=head[0][u];i;i=s[0][i].next)
if((y=s[0][i].to)!=fa){
if(!dfn[y]){
tarjan(y,u);
low[u]=min(low[u],low[y]);
}
else
if(ins[y])
low[u]=min(low[u],dfn[y]);
}
if(low[u]==dfn[u]){
cnt++;
do{
y=sta[top--];
ins[y]=0;
belong[y]=cnt;
}while(y!=u);
}
}
int edk=0;
int main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
ls[0]=ls[1]=1;
int n,m,a,b;
cin>>n>>m;
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
link(edk,a,b);link(edk,b,a);//连边
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,0);//缩点
for(int i=1;i<=n;i++)
for(int j=head[edk][i],y;j;j=s[edk][j].next)
if(getf(i)!=getf(y=s[edk][j].to)&&!pc[getf(i)][getf(y)]){
pc[getf(i)][getf(y)]=1;
link(edk^1,getf(i),getf(y));
ind[getf(y)]++;//找叶子节点
}
int ans=1;
for(int i=1;i<=cnt;i++) ans+=ind[i]==1;//连接它的边只有1个即叶子
printf("%d",ans/2);
return 0;
}
强
%%%