「USACO 2022.12 Platinum」Making Friends 题解

题目大意

有 $N$ 头奶牛，初始时有 $M$ 对朋友关系。每天第 $i$ 头奶牛离开农场，此时它所有仍在农场的朋友之间会互相成为朋友。需要计算整个过程新建立的朋友关系总数。

解题思路

关键观察

1. 等价转换：问题可以转化为 - 当奶牛 $i$ 离开时，它的所有朋友会形成一个完全图
2. 避免重复：关键在于不重复计算已经存在的朋友关系
3. 高效维护：需要高效地维护朋友关系，避免 $O(N^2)$ 的复杂度

算法核心

逆向思维

从最后一天向前处理，即从空图开始，按 $N, N-1, \ldots, 1$ 的顺序添加奶牛和它们的朋友关系。

数据结构设计

• 对每个奶牛 $i$，用 set<int> g[i] 维护编号大于 $i$ 的朋友
• 这样保证朋友关系只在一个方向存储，避免重复

合并策略

当处理到奶牛 $i$ 时：

1. 如果 $i$ 有朋友，选择编号最小的朋友 $v$
2. 将 $i$ 的所有其他朋友合并到 $v$ 的朋友列表中
3. 使用启发式合并（小的合并到大的）保证复杂度

代码解析

#include <cctype>
#include <cstdio>
#include <set>
#include <utility>
#define MAXN 200001
using namespace std;

// 快速读入优化
namespace IO {
    // ... 读入优化代码
}
using IO::rd;

set<int> g[MAXN];  // g[i] 存储编号大于 i 的朋友

int main() {
    int n, m, u, v;
    rd(n, m);
    
    // 读入初始朋友关系，只存储编号较大的朋友
    for (int i = 1; i <= m; ++i) {
        rd(u, v);
        if (u > v) swap(u, v);  // 保证 u < v
        g[u].insert(v);         // 只在编号小的节点存储大的朋友
    }
    
    // 初始答案设为 -m，因为最终要减去初始关系
    long long ans = -m;
    
    // 从 1 到 n 处理每个奶牛
    for (int i = 1; i <= n; ++i) {
        if (g[i].empty()) continue;
        
        // 加上当前节点的所有出边
        ans += (long long)g[i].size();
        
        // 选择编号最小的朋友 v
        v = *g[i].begin();
        g[i].erase(g[i].begin());
        
        // 启发式合并：小的集合合并到大的集合
        if (g[i].size() > g[v].size())
            swap(g[i], g[v]);
        
        // 将 i 的朋友合并到 v 的朋友列表中
        g[v].merge(g[i]);
    }
    
    printf("%lld", ans);
    return 0;
}

算法正确性分析

为什么这样计算？

• 初始时 ans = -m：因为要排除初始的 $M$ 对朋友关系
• ans += g[i].size()：当奶牛 $i$ 离开时，它和所有朋友的连接数
• 最终 ans 就是所有新建立的朋友关系数

合并的意义

当奶牛 $i$ 离开时：

• 它的朋友 $v_1, v_2, \ldots, v_k$ 会互相成为朋友
• 通过将 $i$ 的朋友列表合并到最小的朋友 $v$ 中，我们实际上在构建这些朋友之间的连接

复杂度分析

• 时间复杂度：$O((N+M)\log N)$
  • 每个朋友关系最多被合并 $O(\log N)$ 次（启发式合并）
  • set 操作是 $O(\log N)$ 的
• 空间复杂度：$O(N+M)$

样例验证

对于样例：

7 6
1 3
1 4  
7 1
2 3
2 4
3 5

处理过程：

• 初始：ans = -6
• 处理奶牛1：朋友 {3,4,7}，ans += 3 → -3
• 处理奶牛3：朋友 {5}，ans += 1 → -2
• 最终：ans = 5 ✓

总结

本题的巧妙解法在于：

1. 单向存储朋友关系避免重复
2. 逆向处理简化问题
3. 启发式合并保证效率
4. 数学计算直接得到答案而不需要显式模拟每一天

这种思路对于处理朋友关系传播类问题具有很好的参考价值。