HDU 4612 Warm up (边双连通分量+DP最长链)

【题意】给定一个无向图，问在允许加一条边的情况下，最少的桥的个数

【思路】对图做一遍Tarjan找出桥，把双连通分量缩成一个点，这样原图就成了一棵树，树的每条边都是桥。然后在树中求最长链，这样在两端点间连一条边就能形成环从而减少桥数。

不能更逗比。。多校第一场刚做出来的找最长链第二场就做错了= =，还一直以为是模板的问题。。。。。。

#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)/2)
#define mem(a,b) memset(a,b,sizeof(a))
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
const int MAXV = 200005;
const int MAXE = 2000005;
struct node{
int u, v;
int next;
bool bridge;
}arc[MAXE];
int cnt, head[MAXV];
void init(){
cnt = 0;
mem(head, -1);
return ;
}
void add(int u, int v){
arc[cnt].u = u;
arc[cnt].v = v;
arc[cnt].next = head[u];
arc[cnt].bridge = false;
head[u] = cnt ++;
arc[cnt].u = v;
arc[cnt].v = u;
arc[cnt].next = head[v];
arc[cnt].bridge = false;
head[v] = cnt ++;
return ;
}
int id, dfn[MAXV], low[MAXV];
int bridge_num;
bool vis_arc[MAXE]; //一条边无向边(两个有向边)只访问一次，
void tarjan(int u){
dfn[u] = low[u] = ++ id;
for (int i = head[u]; i != -1; i = arc[i].next){
if (vis_arc[i]) continue;
int v = arc[i].v;
vis_arc[i] = vis_arc[i^1] = 1;
if (!dfn[v]){
tarjan(v);
low[u] = min(low[u], low[v]);
if (dfn[u] bcc[MAXV];

void fill(int u){
bcc[bcc_num].push_back(u);
mark[u] = bcc_num;
for (int i = head[u]; i != -1; i = arc[i].next){
if (arc[i].bridge) continue;
int v = arc[i].v;
if (mark[v] == 0)
fill(v);
}
}
void find_bcc(int n){
mem(vis, 0);
mem(mark, 0);
//确定每个点所属边双联通分量
for (int i = 1; i max1){
max2 = max1;
max1 = dp[bccv];
}
else{
if (dp[bccv] > max2){
max2 = dp[bccv];
}
}
}
}
}
}
if (0 == num){
dp[bccu] = 0;
}
else{
if (num == 1)
maxlong = max(maxlong, max1+1);
else
maxlong = max(maxlong, max1+max2+2);
dp[bccu] = max1 + 1;
}
return ;
}
int n, m;
int main(){
while(scanf("%d %d", &n, &m) != EOF){
if (n + m == 0)
break;
init();
for (int i = 0; i