华为OD机试：找城市

题目描述

一张地图上有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.首先根据输入构建一个无向图，表示城市之间的连接关系。

2.对于每个城市i，计算切断通往该城市的所有道路后，地图上将分为多个连通的城市群的聚集度DPi。

3.找出DP值最小的城市j，即满足条件的城市。

4.如果有多个城市都满足条件，按照编号升序输出这些城市。

JavaScript算法源码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const n = parseInt(await readline());

  const relations = [];
  for (let i = 0; i < n - 1; i++) {
    relations.push((await readline()).split(" ").map(Number));
  }

  console.log(getMinDP(relations, n));
})();

function getMinDP(relations, n) {
   let minDp = Infinity;
   let city = [];

   for (let i = 1; i <= n; i++) {
      const ufs = new UnionFindSet(n + 1);

    for (let [x, y] of relations) {
       if (x === i || y === i) continue;
       ufs.union(x, y);
    }

     const cnts = new Array(n + 1).fill(0);
    for (let j = 1; j <= n; j++) {
      const fa = ufs.find(j);
      cnts[fa]++;
    }

     const dp = Math.max(...cnts);

    if (dp < minDp) {
      minDp = dp;
      city = [i];
    } else if (dp === minDp) {
      city.push(i);
    }
  }

   city.sort((a, b) => a - b);
  return city.join(" ");
}
 
class UnionFindSet {
  constructor(n) {
    this.fa = new Array(n).fill(0).map((_, idx) => idx);
  }

  find(x) {
    if (x !== this.fa[x]) {
      return (this.fa[x] = this.find(this.fa[x]));
    }
    return x;
  }

  union(x, y) {
    let x_fa = this.find(x);
    let y_fa = this.find(y);

    if (x_fa !== y_fa) {
      this.fa[y_fa] = x_fa;
    }
  }
}

Java算法源码
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;

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

    int[][] relations = new int[n - 1][2];
    for (int i = 0; i < n - 1; i++) {
      relations[i][0] = sc.nextInt();
      relations[i][1] = sc.nextInt();
    }

    System.out.println(getResult(n, relations));
  }

  public static String getResult(int n, int[][] relations) {
     int minDp = Integer.MAX_VALUE;
     ArrayList<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];
         if (x == i || y == i) continue;
         ufs.union(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().orElse(0);

       if (dp < minDp) {
        minDp = dp;
        city = new ArrayList<>();
        city.add(i);
      } else if (dp == minDp) {
        city.add(i);
      }
    }

     city.sort((a, b) -> a - b);
    StringJoiner sj = new StringJoiner(" ");
    for (Integer c : city) {
      sj.add(c + "");
    }
    return sj.toString();
  }
}

 class UnionFindSet {
  int[] fa;

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

  public int find(int x) {
    if (this.fa[x] != x) {
      return this.fa[x] = this.find(this.fa[x]);
    }
    return x;
  }

  public void union(int x, int y) {
    int x_fa = this.find(x);
    int y_fa = this.find(y);

    if (x_fa != y_fa) {
      this.fa[y_fa] = x_fa;
    }
  }
}

Python算法源码
import sys

n = int(input())
relations = [list(map(int, input().split())) for i in range(n - 1)]

class UnionFindSet:
    def __init__(self, n):
        self.fa = [i for i in range(n)]

    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]

    def union(self, x, y):
        x_fa = self.find(x)
        y_fa = self.find(y)
        if x_fa != y_fa:
            self.fa[y_fa] = x_fa

def getResult():
    minDp = sys.maxsize
    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 < minDp:
            minDp = dp
            city = [i]
        elif dp == minDp:
            city.append(i)

    city.sort()
    return " ".join(map(str, city))

print(getResult())

C算法源码
 #include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct {
    int *fa;
} UFS;

UFS *new_UFS(int n) {
    UFS *ufs = (UFS *) calloc(1, sizeof(UFS));
    ufs->fa = (int *) calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) {
        ufs->fa[i] = i;
    }
    return ufs;
}

int find_UFS(UFS *ufs, int x) {
    if (x != ufs->fa[x]) {
        ufs->fa[x] = find_UFS(ufs, ufs->fa[x]);
    }
    return ufs->fa[x];
}

void union_UFS(UFS *ufs, int x, int y) {
    int x_fa = find_UFS(ufs, x);
    int y_fa = find_UFS(ufs, y);
    if (x_fa != y_fa) {
        if (x_fa < y_fa) {
            ufs->fa[y_fa] = x_fa;
        } else {
            ufs->fa[x_fa] = y_fa;
        }
    }
}

int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}

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]);
    }

    int minDp = INT_MAX;

    int city[n];
    int city_size = 0;

    for (int i = 1; i <= n; i++) {
        UFS *ufs = new_UFS(n + 1);

        for (int j = 0; j < n - 1; j++) {
            int x = relations[j][0];
            int y = relations[j][1];
            if (x == i || y == i) continue;
            union_UFS(ufs, x, y);
        }

        int cnts[n + 1];
        for (int k = 0; k <= n; k++) {
            cnts[k] = 0;
        }

        for (int k = 1; k <= n; k++) {
            int fa = find_UFS(ufs, k);
            cnts[fa]++;
        }

        int dp = cnts[1];
        for (int k = 2; k <= n; k++) {
            if (cnts[k] > dp) {
                dp = cnts[k];
            }
        }

        if (dp < minDp) {
            minDp = dp;
            city_size = 0;
            city[city_size++] = i;
        } else if (dp == minDp) {
            city[city_size++] = i;
        }
    }

    qsort(city, city_size, sizeof(int), cmp);

    for (int i = 0; i < city_size; i++) {
        printf("%d", city[i]);
        if (i != city_size - 1) {
            printf(" ");
        }
    }

    return 0;
}