依旧dfs题解 | 鞋带难题

怎么这个题解还是没有dfs的（）

没事还是我来写

本题的思路很简单，就是不断地取最外层（即度数为1的点），将这些点全都删除，再更新一下新的最外层，继续删除，直至所有的点都被删除，这样就结束了awa

代码里还有注释，根据注释看食用效果更佳

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

#define sc second
#define fr first
#define int long long
#define itn long long
#define fro for
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define endl '\n'
#define all(qwq) qwq.begin(), qwq.end()
#define ui unordered_map<int, int>
#define pq priority_queue
#define pi acos(-1)

// const int dx[4] = {-1, 1, 0, 0};
// const int dy[4] = {0, 0, -1, 1};
// const int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
// const int dy[8] = {1, 1, 1, 0, -1, -1, -1, 0};
// const int dx[12] = {-1, 0, 1, 1, 1, 0, -1, -1, 0, 2, -2, 0};
// const int dy[12] = {1, 1, 1, 0, -1, -1, -1, 0, 2, 0, 0, -2};
// const int mod = 998244353;
// const int mod = 1e9 + 7;

int m, n, k, x, y, num, op, sum = 0, cnt = 0;
string s;
vvi e;
vi vis;
int dfs(vvi &adj, vi °)
{
    vi leaves;
    // 收集当前所有度数为1的叶子节点
    for (int i = 1; i <= deg.size() - 1; ++i)
    {
        if (deg[i] == 1)
        {
            leaves.push_back(i);
        }
    }

    // 没有叶子节点，结束递归
    if (leaves.empty())
    {
        return 0;
    }

    // 处理这一轮的叶子节点：移除它们，并更新邻居度数
    for (int u : leaves)
    {
        if (deg[u] != 1)
            continue; // 避免重复处理
        for (int v : adj[u])
        { // 把所有的邻居的度数减1
            deg[v]--;
        }
        deg[u] = 0; // 标记当前节点已被移除
    }

    // 递归处理下一轮，组数+1
    return dfs(adj, deg) + 1;
}
void _()
{
    cin >> n >> m;

    vector<vector<int>> adj(n + 1); // 邻接表
    vector<int> deg(n + 1, 0);      // 度数数组

    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        deg[a]++;
        deg[b]++;
    }
    int ans = dfs(adj, deg);
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
    int awa = 1;
    // cin >> awa;
    while (awa--)
    {
        _();
    }
    return 0;
}