一. 题目-找城市
一张地图上有n个城市，城市和城市之间有且只有一条道路相连：要么直接相连，要么通过其它城市中转相连（可中转一次或多次）。城市与城市之间的道路都不会成环。
当切断通往某个城市 i 的所有道路后，地图上将分为多个连通的城市群，设该城市 i 的聚集度为 DPi（Degree of Polymerization）, DPi = max(城市群1的城市个数， 城市群2的城市个数, … 城市群m的城市个数)。
请找出地图上 DP 值最小的城市（即找到城市 j，使得 DPj = min(DP1, DP2 … DPn) )
提示：如果有多个城市都满足条件，这些城市都要找出来（可能存在多个解）
提示：DPi 的计算，可以理解为已知一棵树，删除某个节点后，生成的多个子树，求解多个子树节点数的问题。
输入描述：
每个样例：第一行有一个整数N，表示有N个节点。1<=N<=1000
接下来的N-1行每行有两个整数x,y，表示城市x与城市y连接。1<=x, y<=N输出描述：
输出城市的编号。如果有多个，按照编号升序输出。
补充说明：
收起
示例1
输入：
5
1 2
2 3
3 4
4 5
输出：
3
说明：
输入表示的是如下地图：
1 - 2 - 3 - 4 - 5
对于城市3，切断通往3的所有道路后，形成2个城市群[（1,2）,（4,5）]，其聚集度分别都是2。DP3 = 2。 对于城市4，切断通往城市4的所有道路后， 形成2个城市群[ (1,2,3), (5) ]，DP4 = max（3, 1）= 3 。依次类推，切断其它城市的所有道路后，得到的DP都会大于2，因为城市3就是满足条件的城市，输出是3。
示例2
输入：
6
1 2
2 3
2 5
3 4
3 6
输出：
2 3
说明：
输入表示的是如下地图：
6
|
1 - 2 - 3 - 4
|
5
切断通往2的所有道路后，形成3个城市群[（1）,（5），（3,4,6）]，其聚集度分别都是1、1、3，因此DP2 = 3。
切断通往3的所有道路后，形成3个城市群[（1，2,5）,（4），（,6）]，其聚集度分别都是3、1、1，因此DP3 = 3。
切断其它城市的所有道路后，得到的DP都会大于3，因为城市2、3就是满足条件的城市，升序排列输出是2 3
二.解题思路
这个问题是求解在一个无向图中，切断每个节点到其它节点的所有路径后，找到聚集度（Degree of Polymerization，DP）最小的节点。聚集度的定义是切断后形成的城市群中，城市个数的最大值。
解题思路如下：
- 对于每个节点，切断与它相连的边，得到若干个城市群。
- 对每个城市群计算城市个数，找出城市个数的最大值，即为该节点的聚集度DP。
- 找出所有节点中DP值最小的节点，如果有多个节点满足条件，都需要找出来。
具体实现步骤：
- 构建无向图，表示城市之间的连接关系。
- 对每个节点，切断与其相连的边，使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历形成的城市群。
- 计算每个城市群的城市个数，找到最大值作为该节点的DP值。
- 找出所有节点中DP值最小的节点，输出结果。
以上是思路的概括，具体实现可参考给出的代码。在代码中，首先构建了无向图表示城市连接关系，然后通过深度优先搜索（DFS）遍历每个节点，计算切断后形成的城市群的城市个数，最后找到DP值最小的节点。
三.题解代码
Python题解代码
from collections import defaultdict
import sys
lines = [line.strip() for line in sys.stdin.readlines()]
graph = defaultdict(set)
for line in lines[1:]:
nums = [int(num) for num in line.strip().split(" ")]
a, b = nums
graph[a].add(b)
graph[b].add(a)
nodes = set(graph.keys())
def find_max_node_count(target_node: int):
res = 0
all_visited = set()
for node in nodes:
if node in all_visited:
continue
if node == target_node:
continue
stack = [node]
visited = set()
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
all_visited.add(node)
for c in graph[node]:
if c != target_node:
stack.append(c)
res = max(res, len(visited))
return res
array = []
min_dp = 1000000
for node in nodes:
dp = find_max_node_count(node)
min_dp = min(min_dp, dp)
array.append((dp, node))
array.sort()
res = [v for k, v in array if k == min_dp]
print(*res)
JAVA题解代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main {
static List<Integer>[] g; // 图的邻接表表示
static int n, num; // 节点数量和最小的子树节点数量
static List<Integer> res; // 存储最优解的节点列表
static boolean[] vis; // 记录节点是否被访问过的数组
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
g = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
g[i] = new ArrayList<>();
}
// 读取图的边信息
for (int i = 1; i < n; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
g[a].add(b);
g[b].add(a);
}
num = (int) 1e9; // 初始化最小的子树节点数量为一个较大的值
res = new ArrayList<>(); // 存储最优解的节点列表
vis = new boolean[n + 1]; // 记录节点是否被访问过的数组
for (int i = 1; i <= n; i++) {
solve(i); // 枚举切割节点并更新最小的子树节点数量
}
for (int x : res) {
System.out.print(x + " ");
}
}
// 深度优先搜索，计算以节点u为根的子树的节点数量
static int dfs(int u, int fa) {
int cnt = 1; // 当前节点u的节点数量初始化为1
vis[u] = true; // 标记当前节点已经访问过
for (int x : g[u]) {
if (x == fa || vis[x]) continue; // 跳过父节点和已经访问过的节点
cnt += dfs(x, u); // 递归计算子树的节点数量
}
return cnt;
}
// 枚举切割节点并更新最小的子树节点数量
static void solve(int u) {
Arrays.fill(vis, false); // 初始化节点访问数组为未访问
vis[u] = true; // 当前节点被切割
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue; // 跳过已经访问过的节点
cnt = Math.max(cnt, dfs(i, 0)); // 计算以节点i为根的子树的节点数量
}
if (cnt < num) {
res.clear(); // 清空最优解列表
}
if (cnt <= num) {
num = cnt; // 更新最小的子树节点数量
res.add(u); // 将当前切割的节点加入最优解列表
}
}
}
C/C++题解代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
vector<int> g[N];
int n, num;
vector<int> res;
bool vis[N];
// 深度优先搜索，计算以 u 为根的子树节点数量
int dfs(int u, int fa) {
int cnt = 1;
vis[u] = true;
for (int& x : g[u]) {
if (x == fa || vis[x]) continue;
cnt += dfs(x, u);
}
return cnt;
}
// 枚举切除每个节点后的最大子树，更新最小的最大子树数量及对应节点
void solve(int u) {
memset(vis, 0, sizeof vis);
vis[u] = true; // 当前节点被切割
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
cnt = max(cnt, dfs(i, 0));
}
if (cnt < num) {
res.clear();
}
if (cnt <= num) {
num = cnt;
res.push_back(u);
}
}
int main() {
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
num = 1e9;
for (int i = 1; i <= n; i++) { // 枚举切除第 i 个节点的最大子树
solve(i);
}
for (int& x : res) cout << x << " ";
return 0;
}
JS题解代码
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
const N = 1010;
const g = Array.from({ length: N }, () => []); // 图的邻接表表示
let n = 0; // 节点数量
let num = 0; // 最小的子树节点数量
let res = []; // 存储最优解的节点列表
const vis = new Array(N).fill(false); // 记录节点是否被访问过的数组
function dfs(u, fa) {
let cnt = 1; // 当前节点u的节点数量初始化为1
vis[u] = true; // 标记当前节点已经访问过
for (const x of g[u]) {
if (x === fa || vis[x]) {
continue;
}
cnt += dfs(x, u); // 递归计算子树的节点数量
}
return cnt;
}
function solve(u) {
vis.fill(false); // 初始化节点访问数组为未访问
vis[u] = true; // 当前节点被切割
let cnt = 0;
for (let i = 1; i <= n; i++) {
if (vis[i]) {
continue;
}
cnt = Math.max(cnt, dfs(i, 0)); // 计算以节点i为根的子树的节点数量
}
if (cnt < num) {
res = []; // 清空最优解列表
}
if (cnt <= num) {
num = cnt; // 更新最小的子树节点数量
res.push(u); // 将当前切割的节点加入最优解列表
}
}
rl.question('', (input) => {
n = parseInt(input); // 读取节点数量
rl.on('line', (line) => {
const [a, b] = line.split(' ').map(Number);
g[a].push(b); // 构建图的邻接表
g[b].push(a);
});
rl.on('close', () => {
num = 1e9; // 初始化最小的子树节点数量为一个较大的值
for (let i = 1; i <= n; i++) {
solve(i); // 枚举切割节点并更新最小的子树节点数量
}
console.log(res.join(' ')); // 输出最优解节点列表
});
});
代码OJ评判结果
通过测试点
四.代码讲解(Java&Python&C++&JS分别讲解)
Python题解代码解析：
-
导入模块和初始化数据结构：
from collections import defaultdict: 导入 defaultdict 模块，用于构建默认值为集合的字典。import sys: 导入 sys 模块，用于读取标准输入。graph = defaultdict(set): 创建一个字典，表示城市之间的连接关系，每个城市对应一个集合存储与其相连的城市。
-
读取输入并构建图：
lines = [line.strip() for line in sys.stdin.readlines()]: 读取标准输入的所有行，去除每行首尾的空白字符，并存储在 lines 列表中。for line in lines[1:]:: 遍历从第二行开始的每一行。nums = [int(num) for num in line.strip().split(" ")]: 将每行用空格分割后的数字转换为整数，存储在 nums 列表中。a, b = nums: 将两个整数分别赋值给变量 a 和 b，表示城市 a 与城市 b 相连。graph[a].add(b),graph[b].add(a): 在图的连接关系中添加城市 a 与 b 的双向连接。
-
定义函数
find_max_node_count:- 该函数用于计算切断某个节点后，形成的城市群中的城市个数，返回城市个数的最大值。
- 通过深度优先搜索（DFS）遍历城市群，使用栈进行遍历。
- 利用集合记录已经访问的节点，以及所有已经访问的节点。
- 返回城市个数的最大值。
-
遍历所有节点，计算 DP 值：
array = []: 创建一个空列表，用于存储每个节点的 DP 值和节点编号。min_dp = 1000000: 初始化最小的 DP 值为一个较大的值。for node in nodes:: 遍历所有节点。dp = find_max_node_count(node): 调用函数计算切断当前节点后的 DP 值。min_dp = min(min_dp, dp): 更新最小的 DP 值。array.append((dp, node)): 将当前节点的 DP 值和节点编号添加到列表中。
-
排序结果并输出：
array.sort(): 对列表进行排序，按照 DP 值从小到大排序。res = [v for k, v in array if k == min_dp]: 选择 DP 值等于最小 DP 值的节点。print(*res): 输出最终结果，即满足条件的节点编号。
JAVA题解代码解析：
-
导入模块和初始化数据结构：
import java.util.ArrayList;,import java.util.List;,import java.util.Scanner;: 导入 Java 中的相关模块。List<Integer>[] g;,int n, num;,List<Integer> res;,boolean[] vis;: 声明图的邻接表、节点数量、最小的子树节点数量、最优解节点列表和节点访问数组。
-
读取输入并构建图：
n = scanner.nextInt();: 读取节点数量。g = new ArrayList[n + 1];: 初始化邻接表数组。for (int i = 1; i <= n; i++) { g[i] = new ArrayList<>(); }: 初始化每个节点对应的邻接表。
-
定义函数
dfs:- 该函数用于深度优先搜索，计算以节点 u 为根的子树的节点数量。
- 递归遍历每个节点，并计算子树的节点数量。
- 返回当前节点 u 的节点数量。
-
定义函数
solve:- 该函数用于枚举切断每个节点后的最大子树，更新最小的最大子树数量及对应节点。
- 遍历所有节点，调用
dfs计算以当前节点为根的子树节点数量。 - 更新最小的最大子树数量及对应节点。
-
主函数逻辑：
- 读取图的边信息，构建邻接表。
- 初始化 num 为较大的值，res 为存储最优解的列表。
- 枚举每个节点，调用
solve函数更新最小的最大子树数量及对应节点。 - 输出最优解节点列表。
C/C++题解代码解析：
-
导入模块和初始化数据结构：
#include<bits/stdc++.h>: 导入 C++ 标准库的头文件。using namespace std;: 使用标准命名空间。const int N = 1010;: 定义常量 N。vector<int> g[N];: 创建图的邻接表表示。int n, num;,vector<int> res;,bool vis[N];: 声明节点数量、最小的子树节点数量、最优解节点列表和节点访问数组。
-
定义函数
dfs:- 该函数用于深度优先搜索，计算以节点 u 为根的子树的节点数量。
- 递归遍历每个节点，并计算子树的节点数量。
- 返回当前节点 u 的节点数量。
-
定义函数
solve:- 该函数用于枚举切断每个节点后的最大子树，更新最小的最大子树数量及对应节点。
- 遍历所有节点，调用
dfs计算以当前节点为根的子树节点数量。 - 更新最小的最大子树数量及对应节点。
-
主函数逻辑：
- 读取
节点数量和图的边信息，构建邻接表。
- 初始化 num 为较大的值，res 为存储最优解的列表。
- 枚举每个节点，调用
solve函数更新最小的最大子树数量及对应节点。 - 输出最优解节点列表。
JS题解代码解析：
-
导入模块和初始化数据结构：
const readline = require('readline');: 导入 readline 模块，用于逐行读取标准输入。const N = 1010;,const g = Array.from({ length: N }, () => []);: 定义常量 N 和图的邻接表表示。let n = 0;,let num = 0;,let res = [];: 声明节点数量、最小的子树节点数量、最优解节点列表。const vis = new Array(N).fill(false);: 创建节点访问数组。
-
定义函数
dfs:- 该函数用于深度优先搜索，计算以节点 u 为根的子树的节点数量。
- 递归遍历每个节点，并计算子树的节点数量。
- 返回当前节点 u 的节点数量。
-
定义函数
solve:- 该函数用于枚举切断每个节点后的最大子树，更新最小的最大子树数量及对应节点。
- 遍历所有节点，调用
dfs计算以当前节点为根的子树节点数量。 - 更新最小的最大子树数量及对应节点。
-
主函数逻辑：
- 使用 readline 模块逐行读取输入。
- 读取节点数量和图的边信息，构建邻接表。
- 初始化 num 为较大的值，res 为存储最优解的列表。
- 枚举每个节点，调用
solve函数更新最小的最大子树数量及对应节点。 - 输出最优解节点列表。