CF292B Network Topology

本题采用了一个简化的网络拓扑模型，请仔细阅读题目说明，在开发解决方案时作为正式文档使用。 Polycarpus 仍然担任一家大型公司的系统管理员。这家公司的计算机网络由 $n$ 台计算机组成，其中部分计算机之间通过电缆连接。计算机编号为 $1$ 到 $n$。已知任意两台通过电缆直接或间接连接的计算机都是连通的。 Polycarpus 决定查明网络的拓扑结构。网络拓扑是描述网络配置、显示设备位置和连接方式的方案。 Polycarpus 知道三种主要的网络拓扑结构：总线、环形和星形。总线拓扑表示一根共享电缆，所有计算机都与其相连。环形拓扑中，电缆使每台计算机仅与其他两台相连。星形拓扑中，所有计算机都与唯一的中心节点相连。 我们将上述网络拓扑表示为一个连通的无向图。总线拓扑对应图中除两个端点外，其余每个节点的度都是 $2$，只有两个端点的度为 $1$；环形拓扑对应每个节点的度均为 $2$ 的连通图；星形拓扑对应一个中心节点度为 $n-1$，其余所有节点度为 $1$ 的连通图。具体见下图。  （1）— 总线；（2）— 环形；（3）— 星形 你得到了一张连通的无向图，它反映了 Polycarpus 公司计算机网络的实际情况。请帮助他判断该网络属于哪种拓扑结构。如果无法确定，请输出“unknown topology”。

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$4 \leq n \leq 10^5$，$3 \leq m \leq 10^5$），分别表示图中的节点数和边数。接下来的 $m$ 行，每行包含一对以空格分隔的整数 $x_i$、$y_i$（$1 \leq x_i, y_i \leq n$），表示一条连接 $x_i$ 和 $y_i$ 的无向边。 保证给定的图是连通的。任意两点之间至多只有一条边，且不会出现自环。

输出一行，表示所判定的网络拓扑名称。如果是总线拓扑，请输出 "bus topology"；如果是环形拓扑，请输出 "ring topology"；如果是星形拓扑，请输出 "star topology"。如果都不属于以上三种拓扑，请输出 "unknown topology"。

由 ChatGPT 5 翻译