返回目录

题目描述

一张地图上有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

输出描述

输出城市的编号。如果有多个，按照编号升序输出。

示例：

python算法源码

class UnionFindSet:
    def __init__(self, n):
        self.fa = [i for i in range(n)]  # 初始化并查集，每个节点的父节点都是自己
  
    def find(self, x):
        if x != self.fa[x]:  # 如果x不是根节点，则找到x的根节点
            self.fa[x] = self.find(self.fa[x])  # 路径压缩，将x的父节点直接设为根节点，减少查询路径长度
        return self.fa[x]
  
    def union(self, x, y):
        x_fa = self.find(x)  # 找到x的根节点
        y_fa = self.find(y)  # 找到y的根节点
        if x_fa != y_fa:  # 如果x和y不在同一个集合中
            self.fa[y_fa] = x_fa  # 将y的根节点的父节点设为x的根节点，实现合并操作

async def readline():
    return input()  # 异步输入读取

async def main():
    n = int(await readline())  # 读取城市数量
  
    relations = []
    for i in range(n - 1):
        relations.append(list(map(int, (await readline()).split())))  # 读取城市之间的关系
  
    print(get_min_dp(relations, n))  # 输出结果

def get_min_dp(relations, n):
    min_dp = float('inf')  # 初始设为无穷大
    city = []  # 保存最小城市聚集度对应的城市序号
  
    for i in range(1, n + 1):  # 遍历每个城市
        ufs = UnionFindSet(n + 1)  # 初始化并查集
  
        for x, y in relations:  # 遍历城市之间的关系
            if x == i or y == i:  # 如果和当前城市有关系，则忽略
                continue
            ufs.union(x, y)  # 否则合并城市
  
        cnts = [0] * (n + 1)  # 统计各个连通分量的大小
        for j in range(1, n + 1):
            fa = ufs.find(j)  # 找到节点所在的连通分量的根节点
            cnts[fa] += 1  # 统计该连通分量的大小
  
        dp = max(cnts)  # 取最大的连通分量大小作为当前城市切断后的聚集度
  
        if dp < min_dp:  # 如果聚集度小于最小值，则更新最小值和城市序号列表
            min_dp = dp
            city = [i]
        elif dp == min_dp:  # 如果聚集度和最小值相等，则添加到城市序号列表中
            city.append(i)
  
    city.sort()  # 按照序号升序排列
    return ' '.join(map(str, city))  # 返回城市序号列表的字符串表示

if __name__ == "__main__":
    import asyncio
    asyncio.run(main())  # 运行主函数

C算法源码

#include <stdio.h>
#include <stdlib.h>

// 表示并查集的结构体
struct UnionFindSet {
    int *fa; // 存储父节点指针的数组
};

// 创建一个新的并查集
struct UnionFindSet* createUnionFindSet(int n) {
    // 为 UnionFindSet 结构体分配内存
    struct UnionFindSet* ufs = (struct UnionFindSet*)malloc(sizeof(struct UnionFindSet));
    // 为父节点指针数组分配内存
    ufs->fa = (int*)malloc(n * sizeof(int));
    // 将每个元素初始化为其自身的父节点
    for (int i = 0; i < n; i++)
        ufs->fa[i] = i;
    return ufs;
}

// 查找元素 x 所属集合的根节点
int find(struct UnionFindSet* ufs, int x) {
    // 如果 x 不是根节点，则进行路径压缩
    if (ufs->fa[x] != x)
        return ufs->fa[x] = find(ufs, ufs->fa[x]);
    return x;
}

// 合并两个集合（合并操作）
void unionSets(struct UnionFindSet* ufs, int x, int y) {
    int x_fa = find(ufs, x); // 查找包含 x 的集合的根节点
    int y_fa = find(ufs, y); // 查找包含 y 的集合的根节点
    // 如果 x 和 y 属于不同的集合，则将其中一个设为另一个的父节点
    if (x_fa != y_fa)
        ufs->fa[y_fa] = x_fa;
}

// 计算结果
char* getResult(int n, int relations[][2]) {
    int minDp = __INT_MAX__; // 将最小 dp 初始化为可能的最大值
    int* city = NULL; // 存储最小 dp 的城市指针
    int citySize = 0; // 最小 dp 的城市数量

    // 遍历每个城市，确定其对 dp 的影响
    for (int i = 1; i <= n; i++) {
        struct UnionFindSet* ufs = createUnionFindSet(n + 1); // 创建并查集

        // 根据提供的关系合并集合，不包括当前城市 i
        for (int j = 0; j < n - 1; j++) {
            int x = relations[j][0];
            int y = relations[j][1];
            if (x == i || y == i) // 跳过涉及当前城市的关系
                continue;
            unionSets(ufs, x, y);
        }

        int cnts[n + 1]; // 存储每个集合中城市的计数数组
        for (int j = 0; j <= n; j++)
            cnts[j] = 0;

        // 统计每个集合中的城市数量
        for (int j = 1; j <= n; j++)
            cnts[find(ufs, j)]++;

        int dp = 0; // 初始化当前城市的 dp
        // 找到任何集合中城市数量的最大值
        for (int j = 1; j <= n; j++) {
            if (cnts[j] > dp)
                dp = cnts[j];
        }

        // 更新最小 dp 和对应的城市
        if (dp < minDp) {
            minDp = dp;
            citySize = 0;
            free(city);
            city = (int*)malloc(sizeof(int));
            city[citySize++] = i;
        } else if (dp == minDp) {
            city = (int*)realloc(city, (citySize + 1) * sizeof(int));
            city[citySize++] = i;
        }

        free(ufs->fa); // 释放为并查集分配的内存
        free(ufs);
    }

    // 将城市编号转换为字符串格式
    char* result = (char*)malloc(citySize * 4); // 每个数字最多为 4 个字符长
    for (int i = 0; i < citySize; i++) {
        sprintf(result + i * 4, "%d ", city[i]);
    }
    result[citySize * 4 - 1] = '\0'; // 给字符串添加结束符

    free(city); // 释放为城市数组分配的内存
    return result;
}

int main() {
    int n;
    scanf("%d", &n); // 输入城市数量

    int relations[n - 1][2]; // 存储城市之间的关系
    // 输入关系
    for (int i = 0; i < n - 1; i++)
        scanf("%d %d", &relations[i][0], &relations[i][1]);

    // 计算结果
    char* result = getResult(n, relations);
    printf("%s\n", result); // 输出结果

    free(result); // 释放为结果字符串分配的内存
    return 0;
}

Java算法源码

import java.util.*;

// 并查集实现
class UnionFindSet {
    int[] fa;

    public UnionFindSet(int n) {
        fa = new int[n];
        for (int i = 0; i < n; i++) fa[i] = i;
    }

    // 寻找根节点
    public int find(int x) {
        if (x != fa[x]) {
            fa[x] = find(fa[x]);
            return fa[x];
        }
        return x;
    }

    // 合并两个节点所在的集合
    public void merge(int x, int y) {
        int xFa = find(x);
        int yFa = find(y);

        if (xFa != yFa) {
            fa[yFa] = xFa;
        }
    }
}

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

        // 存储城市间的关系
        int[][] relations = new int[n - 1][2];
        for (int i = 0; i < n - 1; i++) {
            relations[i][0] = scanner.nextInt();
            relations[i][1] = scanner.nextInt();
        }

        // 记录最小dpi
        int minDp = Integer.MAX_VALUE;
        // 记录最小dpi对应的切断城市
        List<Integer> city = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            // 使用并查集进行城市关联
            UnionFindSet ufs = new UnionFindSet(n + 1);

            for (int[] relation : relations) {
                int x = relation[0];
                int y = relation[1];

                // 如果x或y是被切断城市，则对应连接关系不成立
                if (x == i || y == i) continue;

                // 否则连接x和y
                ufs.merge(x, y);
            }

            // 统计每个城市所在集合的大小
            int[] cnts = new int[n + 1];
            for (int j = 1; j <= n; j++) {
                int fa = ufs.find(j);
                cnts[fa]++;
            }

            // 找到最大集合的大小
            int dp = Arrays.stream(cnts).max().getAsInt();

            // 更新最小dpi和对应的切断城市列表
            if (dp < minDp) {
                minDp = dp;
                city.clear();
                city.add(i);
            } else if (dp == minDp) {
                city.add(i);
            }
        }

        // 按照编号升序输出切断城市列表
        Collections.sort(city);

        for (int item : city) {
            System.out.print(item + " ");
        }
        System.out.println();
    }
}