当前位置：首页 > news >正文

隔离网络(JAVA)

news 2025/7/2 5:42:25

题目描述

小蓝负责一家科技公司的数据中心安全。该数据中心包含 $N$ 台服务器，编号为 $1$ 到 $N$ ，以及 $M$ 条数据链路，编号为 $1$ 到 $M$ 。每条数据链路都连接着两台服务器。

最近，数据中心遭到了网络攻击，病毒正在通过这些链路快速蔓延。为了阻止病毒扩散，小蓝需要采取紧急措施，对网络进行隔离。他计划进行一系列操作，每次操作都包含以下两个步骤：

确定当前网络中所有连通的服务器集群——即通过链路直接或间接相连的服务器集合。
对于每个连通的服务器集群，禁用该集群内编号最小的那条数据链路，以切断病毒传播的途径。

小蓝会重复执行上述操作，直到数据中心的所有数据链路都被禁用、整个数据中心的网络都被隔离。对此，请你帮助小蓝计算出，他总共需要进行多少次操作？

输入格式

输入数据第一行包含两个正整数 $N$ 和 $M$ ，分别表示服务器的数量和数据链路的数量。

接下来 $M$ 行，每行包含两个正整数 $u_i$ 和 $v_i$ ，表示第 $i$ 条数据链路连接的服务器编号。数据链路的编号按照输入顺序从上到下依次为 $1$ 到 $M$ 。

输出格式

输出一个整数，表示小蓝需要进行的操作次数。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【样例说明】

第一次操作：

识别两个连通的服务器集群：
- 集群 1：服务器 $(1, 2, 3)$
- 集群 2：服务器 $(4, 5)$
对于集群 1，禁用编号最小的链路 $1 - 2$ ；对于集群 2，禁用编号最小的链路 $4 - 5$ 。

第一次操作结束后，仅剩余一个连通的服务器集群：服务器 $(2, 3)$ 。

第二次操作：

识别剩余的连通服务器集群: 服务器 $(2, 3)$ 。
禁用编号最小的链路 $2 - 3$ 。

第二次操作结束后，网络中不再有连通的服务器集群，隔离完成。总共需要 2 次操作。

【评测用例规模与约定】

对于 $40\%$ 的评测用例， $\leq N \leq 10^3$ ， $\leq M \leq \min(\frac{N \times (N-1)}{2}, 2 \times 10^3)$ 。

对于 $100\%$ 的评测用例， $\leq N \leq 10^5$ ， $\leq M \leq \min(\frac{N \times (N-1)}{2}, 2 \times 10^5)$ 。

💻 代码实现（语言：Java）

import java.util.*;public class Main {static int[] parent, size, depth;static int find(int x) {if (parent[x] != x) parent[x] = find(parent[x]);return parent[x];}static void union(int x, int y) {int fx = find(x);int fy = find(y);if (fx == fy) {// 同一个集合内，增加冗余边计数depth[fx]++;} else {// 合并集合，同时更新深度if (size[fx] < size[fy]) {int tmp = fx; fx = fy; fy = tmp;}parent[fy] = fx;size[fx] += size[fy];depth[fx] = Math.max(depth[fx], depth[fy]) + 1;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); // 服务器数量int m = sc.nextInt(); // 边数量int[] u = new int[m];int[] v = new int[m];for (int i = 0; i < m; i++) {u[i] = sc.nextInt();v[i] = sc.nextInt();}parent = new int[n + 1];size = new int[n + 1];depth = new int[n + 1];for (int i = 1; i <= n; i++) {parent[i] = i;size[i] = 1;}int maxDepth = 0;// 从后往前插入边（逆向模拟）for (int i = m - 1; i >= 0; i--) {union(u[i], v[i]);int root = find(u[i]);maxDepth = Math.max(maxDepth, depth[root]);}System.out.println(maxDepth);}
}