lessons/参考实现/02-强连通与双连通/CodeForces-1000E.cpp

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

struct Edge { int to, id; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> edges(m);
    vector<vector<Edge>> g(n);
    for (int id = 0; id < m; ++id) {
        int u, v; cin >> u >> v; --u; --v;
        edges[id] = {u, v};
        g[u].push_back({v, id}); g[v].push_back({u, id});
    }

    vector<int> dfn(n), low(n), parent(n, -1), parent_edge(n, -1);
    vector<size_t> cursor(n);
    vector<bool> bridge(m, false);
    int timer = 0;
    for (int root = 0; root < n; ++root) if (!dfn[root]) {
        vector<int> st{root}; dfn[root] = low[root] = ++timer;
        while (!st.empty()) {
            int u = st.back();
            if (cursor[u] < g[u].size()) {
                Edge e = g[u][cursor[u]++];
                if (e.id == parent_edge[u]) continue;
                if (!dfn[e.to]) {
                    parent[e.to] = u; parent_edge[e.to] = e.id;
                    dfn[e.to] = low[e.to] = ++timer; st.push_back(e.to);
                } else low[u] = min(low[u], dfn[e.to]);
            } else {
                st.pop_back();
                if (parent[u] != -1) {
                    int p = parent[u];
                    if (low[u] > dfn[p]) bridge[parent_edge[u]] = true;
                    low[p] = min(low[p], low[u]);
                }
            }
        }
    }

    vector<int> comp(n, -1);
    int count = 0;
    for (int s = 0; s < n; ++s) if (comp[s] == -1) {
        vector<int> st{s}; comp[s] = count;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            for (Edge e : g[u]) if (!bridge[e.id] && comp[e.to] == -1) {
                comp[e.to] = count; st.push_back(e.to);
            }
        }
        ++count;
    }
    vector<vector<int>> tree(count);
    for (int id = 0; id < m; ++id) if (bridge[id]) {
        auto [u, v] = edges[id];
        tree[comp[u]].push_back(comp[v]); tree[comp[v]].push_back(comp[u]);
    }
    auto farthest = [&](int start) {
        vector<int> dist(count, -1); queue<int> q;
        dist[start] = 0; q.push(start); int best = start;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (dist[u] > dist[best]) best = u;
            for (int v : tree[u]) if (dist[v] == -1) {
                dist[v] = dist[u] + 1; q.push(v);
            }
        }
        return pair<int, int>{best, dist[best]};
    };
    int endpoint = farthest(0).first;
    cout << farthest(endpoint).second << '\n';
}