Codeforces 1000E(Tarjan缩边-双连通分量+树的直径)

Codeforces 1000E
题意：一条路径上必经的边为关键边，现在让你找一条路径，使得其关键边最多，输出最多的数量。
关键边就是无向图中的桥。而桥两边连的连通分量里面不可能有关键边(桥)，所以用 Tarjan 缩边-双连通分量，步骤与有向图相似。然后缩点后就只需要找一条路径最长了，因为缩点了所以最后出来的图就是一个树，所以求树的直径即可。
知识点：
1、一样的代码不要复制，手打
2、缩点，树剖，单调队列注意前后序号的不同，一定要一个字符一个字符的查
3、树的直径就是树中最长路径，长度是树中点对最短距离的最长距离
4、无向图 Tarjan 缩连通分量，留下的边是桥

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using std::cin; using std::cout; using std::endl;

const int MAXN = 300000 + 5;

struct edge {int v, nxt;} ed[MAXN * 2], ED2[MAXN * 2];

int n, m, en, EN2, hd[MAXN], HD2[MAXN];
int bcc_tot, bcc_belong[MAXN], sz, dfn[MAXN], low[MAXN];
std::stack<int > s;

void ins(int x, int y) {ed[++en] = (edge){y, hd[x]}, hd[x] = en;}
void INS2(int x, int y) {ED2[++EN2] = (edge){y, HD2[x]}, HD2[x] = EN2;}

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++sz, s.push(u);
    for (int i = hd[u]; i > 0; i = ed[i].nxt) {
        edge &e = ed[i];
        if (e.v == fa) continue;
        if (!dfn[e.v]) tarjan(e.v, u), low[u] = std::min(low[u], low[e.v]);
        else low[u] = std::min(low[u], dfn[e.v]);//这里最好加上判断是否在栈里，不写也能过 QAQ
    }
    if (low[u] == dfn[u]) {
        int e; bcc_tot++;
        do {
            e = s.top(); s.pop();
            bcc_belong[e] = bcc_tot;
        } while (e != u);
    }
}

int dis[MAXN];
void dfs(int u, int fa) {
    dis[u] = dis[fa] + 1;
    for (int i = HD2[u]; i > 0; i = ED2[i].nxt) {
        edge &e = ED2[i];
        if (e.v != fa) dfs(e.v, u);
    }
}

void clean() {
    en = EN2 = 0;
    ms(hd, 0), ms(HD2, 0);
    scc_tot = sz = 0, ms(dfn, 0);
}
int solve() {
    clean();
    for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y), ins(y, x);
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0);
    for (int u = 1; u <= n; u++) {
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (bcc_belong[u] != bcc_belong[e.v]) INS2(bcc_belong[u], bcc_belong[e.v]);
        }
    }
    ms(dis, 0); dfs(1, 0);
    int S = 1; for (int i = 2; i <= bcc_tot; i++) if (dis[i] > dis[S]) S = i;
    dfs(S, 0);
    int T = 1; for (int i = 2; i <= bcc_tot; i++) if (dis[i] > dis[T]) T = i;
    printf("%d\n", dis[T] - 1);
    return 0; 
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}