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

【思路】对图做一遍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