洛谷题单指南-连通性问题-CF1000E We Need More Bosses

原题链接：https://www.luogu.com.cn/problem/CF1000E

题意解读：无向图，找到两点之间必须经过的最多的边数。

解题思路：

什么边不是必须经过的边？必然是有不止一条路径可以从一点走到另一点，边双连通分量具备这样的特点！

那么问题，就变成了，两点之间必须经过的边都是除了边双连通分量之外的边，即割边。

可以将边双连通分量进行缩点，然后求最长距离，即直径。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 600005, M = 1200005;
int head1[N], head2[N], to[M], nxt[M], idx; //head1：原图 head2：缩点图
int dfn[N], low[N], timestamp;
stack<int> stk;
int ebcc[N], cnt; //边双
bool cut[M]; //割边
int st, ed, ans; //距离最远的起点st，终点ed，距离ans
int n, m;

void add(int head[], int a, int b)
{
    to[++idx] = b;
    nxt[idx] = head[a];
    head[a] = idx;
}

void tarjan(int u, int p)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    for(int i = head1[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == p) continue;
        if(!dfn[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);

            if(low[v] > dfn[u])
            {
               cut[i] = true; //标记割边
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }

    if(low[u] == dfn[u])
    {
        cnt++;
        while(true)
        {
            int t = stk.top(); stk.pop();
            ebcc[t] = cnt;
            if(t == u) break;
        }
    }
}

void build()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = head1[i]; j; j = nxt[j])
        {
            if(cut[j])
            {
                int u = ebcc[i], v = ebcc[to[j]];
                if(u != v)
                {
                    add(head2, u, v), add(head2, v, u);
                }
            }
        }
    }
}

void dfs(int u, int p, int d)
{
    if(d > ans)
    {
        ans = d;
        ed = u;
    }
    for(int i = head2[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == p) continue;
        dfs(v, u, d + 1);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(head1, u, v), add(head1, v, u);
    }
    tarjan(1, 0); //求割边和边双
    build(); //缩点

    st = 1;
    dfs(st, 0, 0); 
    st = ed, ans = 0;
    dfs(st, 0, 0); //两次dfs法求直径
    cout << ans;
    return 0;
}