Description
给出一个图,求添加一条边使得添加后的图的桥(割边)最少.
Sol
Tarjan.
一遍Tarjan求割边.
我们发现连接的两个点一定是这两个点之间的路径上的桥最多,然后就可以贪心的搞.
Tarjan的同时记录一下到该点的桥个数的最大值和次大值,然后统计答案就可以.
注意要满足这两个点不能再DFS路径上有公共边,意思就是说在每次回溯的时候统计一下最大值和次大值.
Code
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std; const int N = 10005; int n,m,cnt,ans,fr=1,to=1;
vector<int> h[N];
int dfsn[N],low[N];
int f[N][3],g[N][3]; inline int in(int x=0,char ch=getchar()){ while(ch>'9' || ch<'0') ch=getchar();
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
void Tarjan(int u,int fa){
dfsn[u]=low[u]=++cnt,g[u][1]=u;
int cf=0;
for(int i=0,v;i<h[u].size();i++) if((v=h[u][i])!=fa||(v==fa && cf>0)){
if(!dfsn[v]){
Tarjan(v,u);
if(dfsn[u] < low[v]){
if(f[v][1]+1 > ans) ans=f[v][1]+1,fr=u,to=g[v][1];
if(f[u][1] < f[v][1]+1) f[u][2]=f[u][1],g[u][2]=g[u][1],f[u][1]=f[v][1]+1,g[u][1]=g[v][1];
else if(f[u][2] < f[v][1]+1) f[u][2]=f[v][1]+1,g[u][2]=g[v][1];
}else{
if(f[u][1] < f[v][1]) f[u][2]=f[u][1],g[u][2]=g[u][1],f[u][1]=f[v][1],g[u][1]=g[v][1];
else if(f[u][2] < f[v][1]) f[u][2]=f[v][1],g[u][2]=g[v][1];
}low[u]=min(low[u],low[v]);
}else low[u]=min(low[u],dfsn[v]);
}else cf++;
if(f[u][1] > ans) ans=f[u][1],fr=u,to=g[u][1];
if(f[u][1]+f[u][2] > ans) ans=f[u][1]+f[u][2],fr=g[u][1],to=g[u][2];
}
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=in(),m=in();
for(int i=1,u,v;i<=m;i++){
u=in(),v=in();
h[u].push_back(v),h[v].push_back(u);
}
Tarjan(1,0);
// cout<<ans<<endl;
cout<<fr<<" "<<to<<endl;
return 0;
}