CF1000E We Need More Bosses

题意

给定一个 n 点 m 边的无向图，找到 s 和 t 使得从 s 到 t 的路径上必须经过的边数最多。求这个最多边数。

思路

必须经过的边即指割边。因此可以考虑把每个边双连通分量缩成一个点，不难发现其生成的必然是一棵树（不能有环，有环了就还有边双）。树上的各个边都是割边，而我们要寻找的是最大的割边边数，因此考虑找这棵树的直径。

写这种实现较为复杂的题的代码的时候一定要保持思路清晰：

• Tarjan 找出每个点属于的边双
• 建立新树
• 在新树上挑一个点找到直径的一个端点
• 找到直径的另一个端点

这里使用了 namespace 以保持随时思路清晰（

#include <cstdio>
#include <cctype>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int min(int a, int b) {return a < b ? a : b;}

const int maxn = 3e5 + 5;

namespace before
{
    int head[maxn], to[maxn << 1], nxt[maxn << 1], cnt = 1;
    int bel[maxn], dfn[maxn], low[maxn], idx;
    int stk[maxn], top = 0, newtot;

    void add(int u, int v)
    {
        to[++cnt] = v;
        nxt[cnt] = head[u];
        head[u] = cnt;
        return;
    }

    void tarjan(int u, int from)
    {
        dfn[u] = low[u] = ++idx;
        stk[++top] = u;
        for (int i = head[u]; i; i = nxt[i])
        {
            int &v = to[i];
            if (i == (from ^ 1)) continue;
            if (!dfn[v])
            {
                tarjan(v, i);
                low[u] = min(low[u], low[v]);
            }
            else low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u])
        {
            ++newtot;
            int _u;
            do
            {
                _u = stk[top--];
                bel[_u] = newtot;
            } while (u != _u);
        }
        return;
    }
}

namespace after
{
    int head[maxn], to[maxn << 1], nxt[maxn << 1], cnt;

    void add(int u, int v)
    {
        to[++cnt] = v;
        nxt[cnt] = head[u];
        head[u] = cnt;
        return;
    }

    int d, maxdist;

    void dfs(int u, int fa, int dist)
    {
        if (dist > maxdist)
            d = u, maxdist = dist;
        for (int i = head[u]; i; i = nxt[i])
        {
            int &v = to[i];
            if (v == fa)
                continue;
            dfs(v, u, dist + 1);
        }
        return;
    }
}

namespace before
{
    bool vis[maxn];
    void dfs(int u, int fa)
    {
        vis[u] = 1;
        for (int i = head[u]; i; i = nxt[i])
        {
            int &v = to[i];
            if (vis[v]) continue;
            if (bel[u] != bel[v])
            {
                after::add(bel[u], bel[v]);
                after::add(bel[v], bel[u]);
            }
            dfs(v, u);
        }
        return;
    }
}

int main()
{
    int n = read(), m = read();
    FOR(i, 1, m)
    {
        int u = read(), v = read();
        before::add(u, v);
        before::add(v, u);
    }
    before::tarjan(1, -1);
    before::dfs(1, 0);
    after::dfs(1, 0, 0);
    after::maxdist = 0;
    after::dfs(after::d, 0, 0);
    printf("%d\n", after::maxdist);
    return 0;
}