1 条题解

  • 0
    @ 2024-10-31 20:37:19
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 3e5 + 5;
    
    int n, m, dfn[maxn], low[maxn], idx, dcc, id[maxn];
    stack<int> stk;
    vector<int> g[maxn], G[maxn];
    
    void tarjan(int u, int p) {
        dfn[u] = low[u] = ++idx;
        stk.push(u);
        for (auto v : g[u]) {
            if (v == p) continue;
            if (!dfn[v])
                tarjan(v, u), low[u] = min(low[u], low[v]);
            else
                low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            dcc++;
            int v;
            do {
                v = stk.top();
                stk.pop();
                id[v] = dcc;
            } while (v != u);
        }
    }
    
    void build_new_grapph() {
        set<pair<int, int>> st;
        for (int u = 1; u <= n; u++) {
            for (auto v : g[u]) {
                int uu = id[u], vv = id[v];
                if (uu != vv && !st.count({uu, vv})) {
                    st.insert({uu, vv});
                    st.insert({vv, uu});
                    G[uu].push_back(vv);
                    G[vv].push_back(uu);
                }
            }
        }
    }
    
    int dis[maxn];
    
    void dfs(int u, int p, int d) {
        dis[u] = d;
        for (auto v : G[u])
            if (v != p)
                dfs(v, u, d+1);
    }
    
    int main() {
        scanf("%d%d", &n, &m);
        while (m--) {
            int u, v;
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        tarjan(1, -1);
    //    test();
        build_new_grapph();
        dfs(1, -1, 0);
        int p = 1;
        for (int i = 1; i <= dcc; i++)
            if (dis[i] > dis[p])
                p = i;
    //    test2();
        dfs(p, -1, 0);
        int ans = 0;
        for (int i = 1; i <= dcc; i++)
            ans = max(ans, dis[i]);
    //    test2();
        printf("%d\n", ans);
        return 0;
    }
    
    
    • 1

    信息

    ID
    70
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    8
    已通过
    2
    上传者