探索宇宙中的星系联盟

题意

宇宙中有 $n$ 个星系，每个星系有一个名称和一个文明等级（正整数，各不相同）。星系之间有 $m$ 条双向航道。通过航道直接或间接相连的星系构成一个"星系联盟"，联盟的总实力等于其中所有星系文明等级之和。

求总实力最强的联盟中，文明等级最高的星系名称，以及该联盟的总实力。题目保证最强联盟唯一。

思路

看到"直接或间接相连"这个描述，你想到了什么？没错，就是图的连通分量。

怎么求连通分量？两种经典方式：BFS/DFS，或者并查集。这题用并查集最顺手——边读边合并，最后统计就行。

具体步骤：

读入所有星系，用一个 map 把星系名称映射到编号。
初始化并查集，每个星系自成一组。
读入每条航道，把两端星系所在的集合合并。
遍历所有星系，按根节点分组，累加每个连通分量的总实力。
找到总实力最大的连通分量，再在该分量中找文明等级最高的星系。

并查集加路径压缩，单次操作近似 $O(1)$ ，整体非常高效。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int par[100005];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void unite(int a, int b) { par[find(a)] = find(b); }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<string> name(n);
    vector<long long> level(n);
    map<string, int> id;
    for(int i = 0; i < n; i++){
        cin >> name[i] >> level[i];
        id[name[i]] = i;
        par[i] = i;
    }
    int m;
    cin >> m;
    while(m--){
        string a, b;
        cin >> a >> b;
        unite(id[a], id[b]);
    }
    map<int, long long> sumPower;
    for(int i = 0; i < n; i++)
        sumPower[find(i)] += level[i];

    int bestRoot = -1;
    long long bestSum = -1;
    for(auto &[root, s] : sumPower)
        if(s > bestSum){ bestSum = s; bestRoot = root; }

    int bestGalaxy = -1;
    long long bestLevel = -1;
    for(int i = 0; i < n; i++)
        if(find(i) == bestRoot && level[i] > bestLevel){
            bestLevel = level[i];
            bestGalaxy = i;
        }
    cout << name[bestGalaxy] << " " << bestSum << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static int[] par;
    static int find(int x) { return par[x] == x ? x : (par[x] = find(par[x])); }
    static void unite(int a, int b) { par[find(a)] = find(b); }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] name = new String[n];
        long[] level = new long[n];
        par = new int[n];
        Map<String, Integer> id = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String[] parts = br.readLine().trim().split("\\s+");
            name[i] = parts[0];
            level[i] = Long.parseLong(parts[1]);
            id.put(name[i], i);
            par[i] = i;
        }
        int m = Integer.parseInt(br.readLine().trim());
        for (int i = 0; i < m; i++) {
            String[] parts = br.readLine().trim().split("\\s+");
            unite(id.get(parts[0]), id.get(parts[1]));
        }
        Map<Integer, Long> sumPower = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int r = find(i);
            sumPower.put(r, sumPower.getOrDefault(r, 0L) + level[i]);
        }
        int bestRoot = -1;
        long bestSum = -1;
        for (Map.Entry<Integer, Long> e : sumPower.entrySet()) {
            if (e.getValue() > bestSum) {
                bestSum = e.getValue();
                bestRoot = e.getKey();
            }
        }
        int bestGalaxy = -1;
        long bestLevel = -1;
        for (int i = 0; i < n; i++) {
            if (find(i) == bestRoot && level[i] > bestLevel) {
                bestLevel = level[i];
                bestGalaxy = i;
            }
        }
        System.out.println(name[bestGalaxy] + " " + bestSum);
    }
}

import sys
from collections import defaultdict

input = sys.stdin.readline

def main():
    n = int(input())
    name = []
    level = []
    idx = {}
    par = list(range(n))

    def find(x):
        while par[x] != x:
            par[x] = par[par[x]]
            x = par[x]
        return x

    def unite(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            par[ra] = rb

    for i in range(n):
        parts = input().split()
        name.append(parts[0])
        level.append(int(parts[1]))
        idx[parts[0]] = i

    m = int(input())
    for _ in range(m):
        parts = input().split()
        unite(idx[parts[0]], idx[parts[1]])

    sum_power = defaultdict(int)
    for i in range(n):
        sum_power[find(i)] += level[i]

    best_root = max(sum_power, key=lambda k: sum_power[k])
    best_sum = sum_power[best_root]

    best_galaxy = -1
    best_level = -1
    for i in range(n):
        if find(i) == best_root and level[i] > best_level:
            best_level = level[i]
            best_galaxy = i

    print(name[best_galaxy], best_sum)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let ptr = 0;
    const n = parseInt(lines[ptr++]);
    const name = [];
    const level = [];
    const id = {};
    const par = new Array(n);
    for (let i = 0; i < n; i++) par[i] = i;

    function find(x) {
        while (par[x] !== x) { par[x] = par[par[x]]; x = par[x]; }
        return x;
    }
    function unite(a, b) { par[find(a)] = find(b); }

    for (let i = 0; i < n; i++) {
        const parts = lines[ptr++].split(/\s+/);
        name.push(parts[0]);
        level.push(parseInt(parts[1]));
        id[parts[0]] = i;
    }
    const m = parseInt(lines[ptr++]);
    for (let i = 0; i < m; i++) {
        const parts = lines[ptr++].split(/\s+/);
        unite(id[parts[0]], id[parts[1]]);
    }

    const sumPower = {};
    for (let i = 0; i < n; i++) {
        const r = find(i);
        sumPower[r] = (sumPower[r] || 0) + level[i];
    }

    let bestRoot = -1, bestSum = -1;
    for (const r in sumPower) {
        if (sumPower[r] > bestSum) { bestSum = sumPower[r]; bestRoot = parseInt(r); }
    }

    let bestGalaxy = -1, bestLevel = -1;
    for (let i = 0; i < n; i++) {
        if (find(i) === bestRoot && level[i] > bestLevel) {
            bestLevel = level[i];
            bestGalaxy = i;
        }
    }
    console.log(name[bestGalaxy] + " " + bestSum);
});

复杂度

时间复杂度： $O(n \cdot \alpha(n) + m \cdot \alpha(n))$ ，其中 $\alpha$ 是反阿克曼函数，路径压缩后近似 $O(n + m)$ 。
空间复杂度： $O(n + m)$ ，并查集数组和名称映射。