Strongest Friendship Group (USACO Gold December 2022)

题目要找到一个节点集合，使得“集合内部的最小度 * 集合大小”最大化。

首先因为 $n$ 较大（ $\leq 2 \cdot 10^5$ ），所以需要 $\mathcal{O}(n \log n)$ 的算法，不能有平方复杂度，bitmask之类的办法更是肯定不行。

每个连通分量之间是无关的，所以可以分开计算。仔细观察和纸上画图，尝试加边、边点，去边、去点之类各种办法后可以发现，在每个连通分量内部，可以从原图开始，不断去掉度最小的节点，以及相应的边，然后在这个过程中间求结果的最大值，就可以得到结果。这个正确的原因是，去掉度最小的点，是让结果上升的唯一办法，所以不断去节点，就是枚举所有可能是最大值的节点组合。

这时尝试实现会发现的问题，是去掉节点后连通分量可能分裂为多个，需要对每个分别求结果。这个是题目的关键点，因为如果naive来跑DFS/DSU对每个连通分量计算，复杂度就变成至少 $\mathcal{O}(nm)$ 。

正解是用千年并查集技巧：按特定顺序来逐步建图。在这里，就是把去节点的顺序预先算出来，然后倒过来把去节点变成加节点，这样每次加入的时候，只有当前连通分量会贡献可能结果，就实现了 $\mathcal{O}(m \log n)$ 的算法。

同样方法可以见并查集中Mootube习题（USACO Gold 2018 January）。

这是挺好的一个题，还是特殊顺序DSU技巧的应用。图上复杂度要求比较高的算法，这是常用的一个办法，需要能够想到。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, m;
const int MAXN=200005;
vector<int> g[MAXN];
set<int> gs[MAXN];
bool vis[MAXN];
ll ans = 0;
set<pi> deg;
vector<int> order;
bool active[MAXN];
int fa[MAXN], sz[MAXN]; // DSU
 
int find(int x) {
    if (x == fa[x])
        return x;
    else
        return fa[x] = find(fa[x]);
}
 
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y)
        fa[x] = y, sz[y] += sz[x];
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--, v--;
        g[u].push_back(v); g[v].push_back(u);
        gs[u].insert(v); gs[v].insert(u);
    }
    for (int i = 0; i < n; i++)
        deg.insert({g[i].size(), i});
 
    while (deg.size()) {    // generate removal order[]
        int x = deg.begin()->second;
        order.push_back(x);
        deg.erase({gs[x].size(), x});
        for (int u: gs[x]) {
            deg.erase({gs[u].size(), u});
            gs[u].erase(x);
            deg.insert({gs[u].size(), u});
        }
    }
    reverse(order.begin(), order.end());
 
    for (int i = 0; i < n; i++)
        fa[i] = i, sz[i] = 1;
 
    for (int x: order) {
        active[x] = true;
        int d = 0;
        for (int u: g[x]) {
            if (!active[u]) continue;
            d++;
            merge(x, u);
        }
        ans = max(ans, (ll)d * sz[find(x)]);
    }
 
    printf("%lld", ans);
    return 0;
}