题目链接

鞋带难题

题目描述

俱乐部聚会上共有 名学生，用 根鞋带将若干学生两两捆绑，每根鞋带连接恰好两名学生。

管理员按以下流程反复清场：

  1. 对所有学生统计其当前捆绑人数（即当前度数）。
  2. 把所有度数为 1 的学生记录下来；若无此类学生则流程结束。
  3. 将这批记录学生作为一组踢出俱乐部，并连同与他们相连的鞋带一起带走。

流程可能重复多次。求最终一共踢出了多少组学生。

解题思路

这个问题可以被抽象成一个图论问题。 名学生可以看作是图中的 个节点， 根鞋带则是连接节点的 条无向边。一个学生的“捆绑人数”就是图中对应节点的度。

题目描述的清场流程本质上是一个不断“剥离”图中度为 1 的节点的过程。每一轮，所有度为 1 的节点被同时移除，这个过程会一直持续，直到图中不再有度为 1 的节点为止（剩下的图可能是一个或多个环，或者所有节点的度都大于1）。我们需要计算这个剥离过程总共进行了多少轮。

这个逐层移除度为特定值的节点的模式，非常适合使用拓扑排序的思想来解决，特别是基于队列的实现方法。我们可以把每一轮移除的节点看作是拓扑排序中的一层。

算法步骤如下：

  1. 图的表示与初始化：

    • 使用邻接表存储图的结构。
    • 使用一个数组 记录每个节点的度数。
    • 初始化一个队列，将所有初始度数为 1 的节点入队。这些节点构成了第一批被移除的学生。

  2. 迭代移除：

    • 当队列不为空时，表示当前还有可以被移除的节点。我们开始新一轮的移除。
    • 每一轮开始时，将组数（轮数）加一。
    • 为了确保一次性处理完同一批次的所有节点，我们记录下当前队列的大小，然后循环相应次数，将这些节点逐一出队。
    • 对于每个出队的节点 ，遍历其所有邻居节点 。由于连接 和 的边被移除了，我们将 的度数减 1。
    • 在更新 的度数后，如果其度数恰好降为 1，说明它成为了下一批待移除的节点，将其加入队列。

  3. 终止条件：

    • 当队列为空时，意味着图中再也没有度为 1 的节点，整个过程结束。此时记录的组数即为最终答案。

整个过程中，每条边和每个节点最多被访问一次，因此算法是高效的。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);
    vector<int> deg(n + 1, 0);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (deg[i] == 1) {
            q.push(i);
        }
    }

    int groups = 0;
    while (!q.empty()) {
        groups++;
        int level_size = q.size();
        set<int> neighbors_affected;

        // 阶段1：处理当前层级的节点，更新度数，并收集所有受影响的邻居
        for (int i = 0; i < level_size; ++i) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                deg[v]--;
                neighbors_affected.insert(v);
            }
        }

        // 阶段2：检查所有受影响的邻居，将度变为1的加入下一轮队列
        for (int v : neighbors_affected) {
            if (deg[v] == 1) {
                q.push(v);
            }
        }
    }

    cout << groups << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        ArrayList<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        int[] deg = new int[n + 1];

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj[u].add(v);
            adj[v].add(u);
            deg[u]++;
            deg[v]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (deg[i] == 1) {
                q.add(i);
            }
        }

        int groups = 0;
        while (!q.isEmpty()) {
            groups++;
            int levelSize = q.size();
            Set<Integer> neighborsAffected = new HashSet<>();

            // 阶段1：处理当前层级的节点，更新度数，并收集所有受影响的邻居
            for (int i = 0; i < levelSize; i++) {
                int u = q.poll();
                for (int v : adj[u]) {
                    deg[v]--;
                    neighborsAffected.add(v);
                }
            }
            
            // 阶段2：检查所有受影响的邻居，将度变为1的加入下一轮队列
            for (int v : neighborsAffected) {
                if (deg[v] == 1) {
                    q.add(v);
                }
            }
        }

        System.out.println(groups);
    }
}

from collections import deque

n, m = map(int, input().split())

adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)

if m > 0:
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
        deg[u] += 1
        deg[v] += 1

q = deque()
for i in range(1, n + 1):
    if deg[i] == 1:
        q.append(i)

groups = 0
while q:
    groups += 1
    level_size = len(q)
    neighbors_affected = set()

    # 阶段1：处理当前层级的节点，更新度数，并收集所有受影响的邻居
    for _ in range(level_size):
        u = q.popleft()
        for v in adj[u]:
            deg[v] -= 1
            neighbors_affected.add(v)
    
    # 阶段2：检查所有受影响的邻居，将度变为1的加入下一轮队列
    for v in neighbors_affected:
        if deg[v] == 1:
            q.append(v)

print(groups)

算法及复杂度

  • 算法：本题的解法是拓扑排序的一种应用。通过广度优先搜索（BFS）的方式，按层级移除度为 1 的节点。
  • 时间复杂度：，其中 是学生数（节点数）， 是鞋带数（边数）。每个节点和每条边都只会被处理一次。
  • 空间复杂度：，主要用于存储图的邻接表、节点的度数以及队列。