/*
给定无向图，求加入一条边后最少剩下多少桥
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define maxm 1000005
struct Edge{
int to,nxt,cut;}edge[maxm<<
1],edge_c[maxm<<
1];
int head[maxn],tot,head_c[maxn],tot_c,n,m,q;
void addedge(
int u,
int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++
;
edge[tot].cut=
0;
}
void add_c(
int u,
int v){
edge_c[tot_c].to=
v;
edge_c[tot_c].nxt=
head_c[u];
head_c[u]=tot_c++
;
}
int dfn[maxn],low[maxn],ind,c[maxn],dcc;
void tarjan(
int u,
int in_edge){
dfn[u]=low[u]=++
ind;
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
int v=
edge[i].to;
if(!
dfn[v]){
tarjan(v,i);
low[u]=
min(low[u],low[v]);
if(dfn[u]<
low[v])
edge[i].cut=edge[i^
1].cut=
1;
}
else if(i!=(in_edge^
1))
low[u]=
min(low[u],dfn[v]);
}
}
void dfs1(
int u){
c[u]=
dcc;
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
int v=
edge[i].to;
if(c[v]||edge[i].cut)
continue;
dfs1(v);
}
}
int dep[maxn],fa[maxn],flag[maxn];
//flag[u]表示u上点的边使割边
void dfs2(
int u,
int pre,
int deep){
dep[u]=deep;fa[u]=pre;flag[u]=
1;
for(
int i=head_c[u];i!=-
1;i=
edge_c[i].nxt){
int v=
edge_c[i].to;
if(v==pre)
continue;
dfs2(v,u,deep+
1);
}
}
void init(){
memset(head,-
1,
sizeof head);
memset(head_c,-
1,
sizeof head_c);
memset(dep,0,
sizeof dep);
memset(fa,0,
sizeof fa);
memset(flag,0,
sizeof flag);
memset(c,0,
sizeof c);
memset(dfn,0,
sizeof dfn);
memset(low,0,
sizeof low);
tot=tot_c=ind=dcc=
0;
}
int main(){
int tt=
0;
while(cin>>n>>
m,n){
init();
for(
int i=
1;i<=m;i++
){
int u,v;
scanf("%d%d",&u,&
v);
addedge(u,v);
addedge(v,u);
}
tarjan(1,
0);
dcc=
0;
//染色
for(
int i=
1;i<=n;i++
)
if(!
c[i]){
++
dcc;
dfs1(i);
}
for(
int i=
0;i<tot;i++){
//缩点
int v=edge[i].to,u=edge[i^
1].to;
if(c[u]==c[v])
continue;
add_c(c[u],c[v]);
}
int Max=-
1,root=
1;
dfs2(root,0,
0);
for(
int i=
1;i<=dcc;i++
)
if(Max<
dep[i]){
Max=
dep[i];
root=
i;
}
memset(dep,0,
sizeof dep);
dfs2(root,0,
0);
for(
int i=
1;i<=dcc;i++
)
Max=
max(Max,dep[i]);
cout<<dcc-
1-Max<<
endl;
}
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/10463942.html
相关资源：各显卡算力对照表！
