题解 | 鞋带难题

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using LL = long long;
constexpr int N = 2e5 + 5;
int n, m;
int in[N], d[N];
vector<int> g[N];

void solve() {
    cin >> n >> m;
    for (int i = 1, x, y; i <= m; ++i) {
        cin >> x >> y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
        in[x]++, in[y]++;
    }
    queue<int> qe;
    for (int i = 1; i <= n; ++i) {
        if (in[i] == 1)qe.emplace(i), d[i] = 1;
    }
    int res = 0;
    while (!qe.empty()) {
        int u = qe.front();
        qe.pop();
        if (in[u])res = max(res, d[u]);
        for (auto v: g[u]) {
            if (--in[v] == 1) {
                qe.emplace(v);
                d[v] = max(d[v], d[u] + 1);
            }
        }
    }
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int tt = 1;
    //    cin >> tt;
    while (tt--) solve();
}