Warm up

我真蠢

这道题wa了一下午，最后后发现是is数组开小了。。。。。。想死

思路：
我们先进行缩点，以桥为边构造成一棵树。
然后我们，求这棵树的最大直径，这就是我们能够消去的最多桥。

代码如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int max_n = 2e5 + 100;
const int max_m = 2e6 + 100;
int N, M;
struct edge {
    int to, rev, next;
}E[max_m << 1];
int head[max_n];
int cnt = 1;
void add(int from, int to, int rev) {
    E[cnt].to = to;E[cnt].rev = rev;
    E[cnt].next = head[from];
    head[from] = cnt++;
}
int dfn[max_n], low[max_n];
int tot = 0;
bool is[max_m];
void tarjan(int u, int fa_id) {
    dfn[u] = low[u] = ++tot;
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (i == fa_id)continue;
        if (!dfn[v]) {
            tarjan(v, E[i].rev);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                is[i] = is[E[i].rev] = true;
        }
        else low[u] = min(low[u], dfn[v]);
    }
}
int color[max_n];
void draw(int u,int c) {
    color[u] = c;
    for (int i = head[u];i;i = E[i].next)
        if (!is[i] && color[E[i].to] == 0)
            draw(E[i].to, c);
}
edge ES[max_m << 1];
int head2[max_n];
int cnt2 = 1;
void add2(int from, int to) {
    ES[cnt2].to = to;
    ES[cnt2].next = head2[from];
    head2[from] = cnt2++;
}
int d[max_n];
bool vis[max_n];
int ans = 0;
void dp(int u) {
    vis[u] = true;
    for (int j = head2[u]; j; j = ES[j].next) {
        int v = ES[j].to;
        if (vis[v]) continue;
        dp(v);
        ans = max(ans, d[u] + d[v] + 1);
        d[u] = max(d[u], d[v] + 1);
    }
}
int main() {
    while (scanf("%d %d", &N, &M) != EOF) {
        if (N == 0 && M == 0)break;
        fill(head, head + max_n, 0);cnt = 1;
        fill(is, is + max_m, false);
        fill(dfn, dfn + max_n, 0);tot = 0;
        fill(color, color + max_n, 0);
        fill(head2, head2 + max_n, 0);cnt2 = 1;
        fill(vis, vis + max_n, false);
        fill(d, d + max_n, 0);
        ans = 0;
        for (int i = 1, u, v;i <= M;++i) {
            scanf("%d %d", &u, &v);
            add(u, v, cnt + 1);
            add(v, u, cnt - 1);
        }tarjan(1, 0);
        int bridge = 0;
        for (int i = 1;i <= N;++i)
            if (color[i] == 0) 
                draw(i, ++bridge);
        for (int u = 1;u <= N;++u)
            for (int i = head[u];i;i = E[i].next)
                if (is[i])
                    add2(color[u], color[E[i].to]);
        dp(1);
        printf("%d\n", bridge - ans - 1);
    }
}