【题目描述】:
蒟蒻刚刚学了点图论,现在他面对一张无向连通图,他想问你:
最少添加多少条边,使得任意两点之间有两条无公共边的路(可以有公共点)。
【输入描述】:
第一行n,m,n个点(编号1--n)m条边;
接下来m行,每行u,v;
表示u到v之间有一条无向边(可能重复描述一条边);
【输出描述】:
一行,即答案。
【样例输入】:
5 5
1 2
2 3
3 4
4 5
4 5
【样例输出】:
1
【时间限制、数据范围及描述】:
时间:1s 空间:256M
20%的数据N<=20, M<=50
40%的数据N<=2000,M<=2000
70%的数据N<=20000,M<=20000
100%的数据N<=50000,M<=50000
本题缩点后将LCA最远的两个叶子结点间加一条边,一直加到整个图联通为止,共要加(leaf+1)/2条边。
Code:
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
int read(){
int x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
int n,m,cnt=1,top,scc,ind;
int last[50005],low[50005],dfn[50005],q[50005],bl[50005];
int d[50005];
bool inq[50005];
struct edge{int to,next;}e[100005];
void insert(int u,int v){
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void tarjan(int x,int fa){
low[x]=dfn[x]=++ind;
q[++top]=x;inq[x]=1;
for(int i=last[x];i;i=e[i].next)
if(i!=(fa^1)){
if(!dfn[e[i].to]){
tarjan(e[i].to,i);
low[x]=min(low[x],low[e[i].to]);
}
else if(inq[e[i].to])
low[x]=min(low[x],dfn[e[i].to]);
}
if(low[x]==dfn[x]){
scc++;
int now=0;
while(x!=now){
now=q[top--];inq[now]=0;
bl[now]=scc;
}
}
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
insert(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i,0);
for(int x=1;x<=n;x++)
for(int i=last[x];i;i=e[i].next)
if(bl[x]!=bl[e[i].to])
d[bl[e[i].to]]++;
int sum=0;
for(int i=1;i<=scc;i++)
if(d[i]==1)sum++;
printf("%d\n",(sum+1)/2);
return 0;
}