小欧皇

[题目链接](https://www.nowcoder.com/practice/6afe13c512d44b30b03933471d259ba4)

思路

有 个城市和 条道路，部分城市已被占领。两个被占领的城市能经商的条件是：它们之间存在一条路径，且路径上所有中间城市都已被占领。每对能经商的城市贡献 1 收益。现在要恰好再占领一个未占领的城市，使总收益最大化，收益相同时选编号最小的城市。

关键观察

"路径上所有中间城市都已被占领"这个条件，等价于只看已占领城市构成的子图。在这个子图中，处于同一连通分量的城市两两都能经商。因此，一个大小为 的连通分量贡献 的收益。

并查集维护连通分量

用并查集维护已占领城市之间的连通关系：只有当边的两个端点都是已占领城市时，才合并它们。这样就得到了所有已占领城市的连通分量及其大小。

基础收益 = 所有已占领城市连通分量的 之和。

枚举新占领的城市

对每个未占领城市 ，考虑占领它后的效果：

1. 找到 的所有已占领邻居所在的不同连通分量（用集合去重根节点）。
2. 这些分量会通过城市 合并成一个大分量，新大小 = 。
3. 新的总收益 = 基础收益 被合并分量原来的收益之和 合并后大分量的 。

取收益最大（相同则编号最小）的城市作为答案。

样例演示

输入：5 个城市，状态 01010（城市 2、4 已占领），边：1-2, 1-3, 1-4, 4-5, 1-5。

• 已占领城市 2 和 4 不直接相连（中间城市 1 未占领），所以是两个独立分量 和 ，基础收益 = 0。
• 占领城市 1：已占领邻居为 2 和 4，合并后分量 ，大小 3，收益 = 。
• 占领城市 3：已占领邻居为空，收益 = 0。
• 占领城市 5：已占领邻居为 4，合并后分量 ，大小 2，收益 = 。
• 最大收益 3，对应城市 1。输出 1 3。

复杂度分析

• 时间复杂度：，其中 是反阿克曼函数，并查集操作近似 。
• 空间复杂度：，存储邻接表和并查集。

代码

C++

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

int par[200005], sz[200005];

int find(int x) {
    while (par[x] != x) x = par[x] = par[par[x]];
    return x;
}

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    for (int i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
    }

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        if (s[u - 1] == '1' && s[v - 1] == '1') {
            unite(u, v);
        }
    }

    long long baseRev = 0;
    vector<bool> counted(n + 1, false);
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '1') {
            int r = find(i);
            if (!counted[r]) {
                counted[r] = true;
                long long k = sz[r];
                baseRev += k * (k - 1) / 2;
            }
        }
    }

    int bestCity = -1;
    long long bestRev = -1;

    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '1') continue;
        set<int> roots;
        for (int nb : adj[i]) {
            if (s[nb - 1] == '1') {
                roots.insert(find(nb));
            }
        }
        long long newSize = 1;
        long long removedRev = 0;
        for (int r : roots) {
            long long k = sz[r];
            removedRev += k * (k - 1) / 2;
            newSize += k;
        }
        long long addedRev = newSize * (newSize - 1) / 2;
        long long totalRev = baseRev - removedRev + addedRev;
        if (totalRev > bestRev) {
            bestRev = totalRev;
            bestCity = i;
        }
    }

    cout << bestCity << " " << bestRev << endl;
    return 0;
}

Java

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

public class Main {
    static int[] par, sz;

    static int find(int x) {
        while (par[x] != x) x = par[x] = par[par[x]];
        return x;
    }

    static void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) { int t = a; a = b; b = t; }
        par[b] = a;
        sz[a] += sz[b];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        String s = br.readLine().trim();

        par = new int[n + 1];
        sz = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj.get(u).add(v);
            adj.get(v).add(u);
            if (s.charAt(u - 1) == '1' && s.charAt(v - 1) == '1') {
                unite(u, v);
            }
        }

        long baseRev = 0;
        boolean[] counted = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) == '1') {
                int r = find(i);
                if (!counted[r]) {
                    counted[r] = true;
                    long k = sz[r];
                    baseRev += k * (k - 1) / 2;
                }
            }
        }

        int bestCity = -1;
        long bestRev = -1;

        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) == '1') continue;
            Set<Integer> roots = new HashSet<>();
            for (int nb : adj.get(i)) {
                if (s.charAt(nb - 1) == '1') {
                    roots.add(find(nb));
                }
            }
            long newSize = 1;
            long removedRev = 0;
            for (int r : roots) {
                long k = sz[r];
                removedRev += k * (k - 1) / 2;
                newSize += k;
            }
            long addedRev = newSize * (newSize - 1) / 2;
            long totalRev = baseRev - removedRev + addedRev;
            if (totalRev > bestRev) {
                bestRev = totalRev;
                bestCity = i;
            }
        }

        System.out.println(bestCity + " " + bestRev);
    }
}