<题目链接>
题目大意：
给出一个连通图，问你在这个连通图上加一条边，使该连通图的桥的数量最小，输出最少的桥的数量。
解题分析：
首先，通过Tarjan缩点，将该图缩成一颗树，树上的每个节点都是一个边双连通分量，树上的每条边都是桥，现在需要挑出两个点，将它们直接相连，这样它们原始路径上所有的桥因为形成了环而全部消失，因此为了使剩下的桥最少，我们需要找到路径上桥最多的两点，又由于缩点后，树的每条边都是桥，所以这里就转化为树上距离两点的最远距离，也就是求树的直径。
下面Tarjan的时候需要注意的是，vis记录的是访问过边的编号不是节点的编号。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef pair<int, int> pll;
;
;
int num, num1, top, cnum,maxdis, pos,cnt;
int head[N], head1[N], dis[N],instk[N], stk[N], dfn[N], low[N], belong[N];
];
struct Edge{
int to, next;
}e[M<<], e1[M<<];
void add(int u, int v) {
e[num].to = v, e[num].next = head[u], head[u] = num++;
}
void add1(int u, int v) {
e1[num1].to = v, e1[num1].next = head1[u], head1[u] = num1++;
}
void init() {
num = num1 = cnt = cnum = top = ;
mem(head,-),mem(head1,-),mem(belong,),mem(instk,);
mem(vis,),mem(stk,),mem(dfn,),mem(low,),mem(dis,);
}
pll edge[M];
void tarjan(int u){
dfn[u] = low[u] = ++cnt;
instk[u] = ;
stk[++top] = u;
for(int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to;
if(vis[i])continue;
vis[i] = vis[i^] = ; //将正、反两边全部标记
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if(instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]) {
++cnum; //cnum为边双连通分量的数量
int v;
do{
v = stk[top--];
instk[v] = ;
belong[v] = cnum; //将该连通块染色
} while(v != u);
}
}
void bfs(int u){
queue <int> q;
q.push(u);
dis[u] = ;
mem(vis,);
vis[u] = ;
maxdis = , pos = u;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = head1[u]; ~i; i = e1[i].next) {
int v = e1[i].to;
if(vis[v])continue;
vis[v] = ;
dis[v] = dis[u]+;
if(dis[v]>maxdis) { //更新树上的最远距离
maxdis = dis[v];
pos = v; //并且记录下该点
}
q.push(v);
}
}
}
int main()
{
int n, m, x, y;
while(scanf("%d%d",&n,&m)!=EOF,n||m){
init();
; i<m; i++) {
scanf("%d%d", &x, &y);
edge[i].first = x, edge[i].second = y; //记录下所有的边，用结构体记录也可以
add(x, y),add(y, x);
}
tarjan();
;
; i<m; i++){ //将缩点后的所有点建图，跑BFS，求树的直径
int x = edge[i].first, y = edge[i].second;
if(belong[x]!=belong[y]) {
add1(belong[x], belong[y]);
add1(belong[y], belong[x]);
edgenum++; //桥的数量+1
}
}
bfs(belong[]);
bfs(pos); //求出此时树的直径，即一条路径上所含的最多桥的数量
int ans = edgenum-maxdis;
printf("%d\n", ans);
}
}
2018-11-07