USACO Tea Time S：从朋友关系到并查集入门

如果让我在USACO历届题目里挑一道“名字最像模拟、考点最不像模拟”的入门题我会选P2978 [USACO10JAN] Tea Time S。这道题的背景是一场下午茶聚会但当你真正动手写代码时就会发现它考察的并不是派对流程而是一个非常经典的数据结构并查集。许多初学者第一次看到这道题第一反应是“朋友关系嘛建个无向图每次询问跑一遍BFS不就行了”——这种思路在数据量小的时候确实能过但一旦把查询次数放大效率立刻崩盘。这篇文章就从这道题出发把并查集的来龙去脉拆开讲清楚顺便分享我在练习这个题时踩过的坑以及它背后可以延伸出的一整类算法题。1. 这道USACO银组题表面在问“能不能一起喝茶”实际在问“在不在一个圈子”1.1 原题梗概下午茶、朋友关系表和传递性规则题目描述很简洁农夫约翰有n头奶牛编号1到n。已知m对直接朋友关系比如“奶牛a和奶牛b是朋友”。现在有k个询问每个询问给出两头奶牛u和v问你它们能否坐在一起喝下午茶。能喝的条件有两层要么它们本来就是直接朋友要么它们通过朋友链间接认识。换句话说“朋友的朋友也是朋友”这个关系可以无限传递下去。这里有一个容易忽略的细节题目说的“能否一起喝下午茶”不是问两头牛之间有没有一条直接边而是问它们是否在同一个“社交圈子”里。只要在同一个圈子里不管中间隔了多少层朋友关系都可以凑一桌。这个“圈子”的概念才是解题的关键。1.2 样例手推把“间接认识”翻译成圈子的合并为了把问题说清楚我重新构造一个更直观的小样例。假设有5头奶牛编号1到5朋友关系有两对1和2是朋友4和5是朋友。接下来有三个询问询问11和3能一起喝茶吗询问22和3能一起喝茶吗询问34和5能一起喝茶吗先看关系。1和2是直接朋友所以它们构成一个小圈子4和5是直接朋友构成另一个小圈子3没有出现在任何关系里所以它自己单独是一个圈子。注意3目前和任何人都没有边即使1认识2、2认识3这种链也不存在所以1和3不在同一圈子询问1输出N。同理2和3也不在同一圈子询问2输出N。而4和5本来就有直接朋友关系它们属于同一圈子询问3输出Y。你可能会说这题目也太简单了直接开一个布尔矩阵标记朋友关系然后每次询问时在里面查一下不就行了问题在于“间接认识”这个条件。假设关系链变成1-2-3-4-5那么1和5虽然没有直接边但通过2、3、4可以互相认识。这时候布尔矩阵的查询就会失效必须想办法把“传递闭包”求出来。1.3 我为什么认为这道题是并查集最好的入门题之一这里面的关系有一个非常漂亮的数学性质朋友关系满足自反性自己当然可以和自自己喝、对称性A是B的朋友B也是A的朋友、传递性朋友的朋友还是朋友。满足这三个条件的关系叫做等价关系等价关系会把一个集合划分成若干个互不相交的“等价类”也就是这里的“朋友圈”。一旦意识到题目在问“等价类”就会发现这件事不需要真的把整条朋友链都存下来。你只需要维护“谁和谁已经被归入同一个圈子”然后每次查询时检查两头牛是否属于同一个圈子即可。这正是并查集数据结构最原生的应用场景。可以说USACO把这道题放在银组就是希望选手在第一次接触“连通性判断”时能自然地想到用并查集来解决而不是陷入图搜索的泥潭。2. 基于图的暴力搜索为什么吃力不讨好2.1 若把关系建模成无向图一次询问可以BFS如果你的第一反应是建图那我完全理解因为“朋友的朋友”这句话太像图的遍历了。把每一头奶牛看成一个节点把每条直接朋友关系看成一条无向边那么“1和5能否间接认识”就等价于“从节点1出发能否走到节点5”。这完全可以对每个询问做一次BFS或DFS来解决。具体的做法是读入所有朋友关系后建立邻接表。对于每一个询问(u, v)写一个BFS从u出发看能不能搜到v。如果搜到了输出Y否则输出N。这个思路没有错在小规模数据下甚至很直观代码量也不大大约20行就能写出来。2.2 询问很多时的复杂度灾难但问题出在扩展性上。假设有n个节点、m条边、k次询问每一次BFS的复杂度是O(nm)因为要遍历节点和邻接表。于是总复杂度是O(k(nm))。当n和m分别达到10^4、k达到10^4级别时总操作量就是10^4乘以2万也就是2×10^8左右的量级这个数字在一般的评测环境里基本要超时了。更重要的是这种做法完全没有利用到之前询问的计算结果。比如你第一次询问发现1和5在同一个圈子第二次又询问1和6虽然两次查询共用了很多相同节点BFS却会把它们重新搜一遍。这种重复计算在数据量稍大时显得特别浪费。作为对比并查集在合并完所有边之后每个查询只需要做两次查找操作均摊复杂度几乎接近O(1)差距一目了然。2.3 “传递性”三个字最终指向等价类划分我们来深挖一下“朋友的朋友也是朋友”这句话到底意味着什么。假设A和B是朋友B和C是朋友那么A和C也是朋友。现在再看C和D如果C和D也是朋友那么B和D也可以成为朋友进而A和D也可以成为朋友。你会发现这种传递关系会把原来零散的节点不断“粘”成更大的团块。只要两个节点之间存在一条任意长度的路径它们最终就会被粘进同一个团块。这个过程和我们在纸上合并集合的过程一模一样不需要保留路径的具体走向。这正是并查集的名字里“并”字的来源将集合合并将关系传递。换句话说这道题要的不是“路径”而是“归属”。BFS求的是路径可达性而本题要的是归属一致性。后者有一个比图搜索轻量得多的工具就是并查集。理解了这个区别你就不会再想着对每个询问跑一遍BFS了。3. 并查集的建立、查找与合并从圈子抽象到树形结构3.1 fa数组就是“每一头牛只记住一个直属上级”并查集的核心想法特别简单把每个圈子乱糟糟的成员关系整理成一颗“管理树”。树根是这个圈子的代表其他节点只需要记住自己的父亲节点是谁。在代码里这个“父亲”关系用一个数组fa来记录fa[x]表示节点x的直接上级。比如一开始所有奶牛都是独立的圈子没有任何朋友关系。这时每头牛就是自己圈子的代表所以fa[i] i。这个初始化步骤非常重要它给每一头牛找到了自己的“根”。如果漏掉这一步所有节点的fa都是默认值0那么在查找时就会陷入死循环找半天也找不到一个合法的根节点。在合并两个圈子时不需要把A圈子所有成员的fa都改成B圈子的代表只需要把A圈子的根节点的fa改成B圈子的根节点就行。其他成员在查询时会自动沿着fa数组一路向上找到新的根节点。这就是为什么并查集的合并操作是O(1)级别的——它只更新一个节点的父亲而不是整个集合。3.2 find顺着上级链找到圈子首席代表查找操作是并查集最核心的部分。给定一个节点x我们希望找到它所在圈子的根节点也就是“首席代表”。实现方法是一个循环或递归一旦发现fa[x] ! x就说明x不是根于是把x替换成fa[x]继续向上找直到找到某个节点r满足fa[r] r为止。int find(int x) { while (fa[x] ! x) x fa[x]; return x; }这段代码看起来简单但在极端情况下可能很慢。假如合并时总是把节点依次接到另一棵树上比如1接到22接到33接到4……最后这棵树就会退化成一条长度为n的链。此时find(1)要循环n次才能找到根查询一次的复杂度就变成了O(n)和暴力BFS没有本质区别了。所以find的写法必须配合优化也就是下面要讲的路径压缩。3.3 unite合并两个圈子时谁并入谁合并操作也很直观找到u的根再找到v的根如果两者不同就把其中一个根接到另一个根上。代码基本是固定模板void unite(int u, int v) { int ru find(u); int rv find(v); if (ru ! rv) fa[ru] rv; }这里有一个值得注意的细节合并的时候是把根节点ru的fa改成rv而不是把u的fa直接改成v。原因是如果只改u的父节点那么u原来所在圈子里的其他节点在查找根时还是会先找到u再从u跳转到v。这样虽然最终也会返回正确结果但是会多走一层无谓的路而且在路径压缩不彻底的情况下会积累很多无效的深度。所以规范写法都是先找根再改根的fa。如果觉得随机合并会影响效率还可以引入按秩合并。所谓“秩”简单理解就是树的高度。再维护一个数组rnkrnk[x]表示以x为根的树的高度。合并时优先把高度较小的树接到高度较大的树上这样能避免树越来越高。如果两棵树高度相同则任意选一棵接到另一棵下面同时被接的那棵树的根节点的高度加1。int rnk[MAXN]; void unite(int u, int v) { int ru find(u); int rv find(v); if (ru rv) return; if (rnk[ru] rnk[rv]) swap(ru, rv); fa[rv] ru; if (rnk[ru] rnk[rv]) rnk[ru]; }3.4 路径压缩与按秩合并让链几乎变成一层路径压缩是并查集性能的灵魂。思路是在find的过程中把沿途经过的所有节点的fa直接指向根节点。这样下一次查找这些节点时只需要一步就能找到根。实现上递归版最简洁int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); // 路径压缩 }这段代码会把x的父亲直接设置成find的返回值也就是根节点。递归返回的过程中沿途每个节点也都会把父亲指向根从而实现整条路径的扁平化。均摊复杂度会降到一个极小的常数级别数学上可以证明接近O(1)。这也是很多教材里“并查集查询几乎O(1)”说法的来源。我个人的建议是入门阶段先写递归版本因为代码短容易理解等熟练之后再考虑改成循环版本熟悉一下非递归写法因为极端情况下递归栈深可能不太安全这个问题我后面还会提到。4. 完整代码、逐行注释与自查清单4.1 C代码全文把上面的内容整合起来这道题的完整AC代码如下。代码不长但每一行都对应着一个容易踩的细节。#include iostream using namespace std; const int MAXN 10005; int fa[MAXN]; int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); // 路径压缩 } void unite(int a, int b) { int ra find(a); int rb find(b); if (ra ! rb) fa[ra] rb; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin n m k; // 初始化每头牛自成一个圈子 for (int i 1; i n; i) fa[i] i; // 读入m条朋友关系合并圈子 for (int i 0; i m; i) { int a, b; cin a b; unite(a, b); } // 处理k个询问 while (k--) { int a, b; cin a b; if (find(a) find(b)) cout Y \n; else cout N \n; } return 0; }4.2 关键行的设计理由不能省略的细节首先初始化循环中fa[i] i索引从1开始而不是0因为题目给的奶牛编号是1到n。如果你从0开始初始化那么编号为1的牛就会访问到fa[0]这个位置虽然没有越界但语义上是错的容易在后续处理中产生奇怪的问题。其次输出判断使用的是find(a) find(b)而不是直接比较fa[a] fa[b]。很多人会在这里偷懒觉得fa数组已经存了父亲直接比较不就行了这其实是错的。因为fa[a]和fa[b]只是两头牛的父亲节点不一定是它们圈子的根节点。比如a的父亲是某个中间节点b的父亲是根节点即使它们属于同一圈子fa[a]也可能不等于fa[b]。只有通过find走到根节点再比较才能保证结果正确。第三我加了ios::sync_with_stdio(false); cin.tie(nullptr);这两行用来加速cin和cout的输入输出。这道题的数据量不算特别大不加也能过但养成这个习惯能让你在后续处理更大数据量的题目时少吃亏。分析一下m条关系加k次查询总输入行数约mk1虽然不大但使用快读总归是稳妥的做法。4.3 提交前5个自查点我整理了自己在练习和给学弟学妹改代码时经常发现的几个问题这5个自查点可以帮助你减少WA或TLE的概率。第一个自查点初始化是否覆盖了全部节点。如果n是1000而你初始化循环只写了i 10那么后面访问到未初始化的fa[i]时find就会无限循环。第二个自查点find是否写了路径压缩。不写路径压缩在数据构造得比较极限的情况下会超时而题目本身并不想卡这个点所以加上肯定没错。第三个自查点unite时是否先find再修改fa。如果忘了找根直接fa[a] b会导致圈子关系错乱出现“部分成员找不到根”的情况。第四个自查点输出格式对不对。题目要求每行输出一个大写字母Y或N不要输出成小写字母也不要输出成“YES”“NO”这种格式这些都会导致格式错误。第五个自查点读入数据顺序是否正确。第一行是n、m、k而不是k、m、n。这种低级错误真的会发生尤其是你从其他语言或模板复制代码的时候务必核对清楚。5. 我在实盘训练中踩过的坑与优化方向5.1 递归find在极端数据下的风险与循环写法递归版本的find代码非常简洁但有一个隐患如果待查找的树高度非常大递归深度也会非常大有可能导致栈溢出。尤其是在一些题目数据刻意构造长链的时候一旦不做按秩合并链的长度就能逼近节点总数。这时递归版find可能在几万层就爆栈了。解决办法是改成循环版find先把根找出来再沿着原路径把所有节点指向根。写起来比递归版复杂一些但稳定性更好int find(int x) { int r x; while (fa[r] ! r) r fa[r]; // 先找到根 while (x ! r) { // 再沿着路径把每个节点直接挂到根上 int t fa[x]; fa[x] r; x t; } return r; }我第一次接触这个循环写法时挺不习惯的觉得“找到根不就行了为什么还要回头走一遍”。后来才明白如果不回头压缩路径下一次查找同一个节点还是得重新走一次长链前面那段while就白费了。两次while的目的一次是找根一次是压缩缺一不可。5.2 统计每个圈子人数在union里顺手维护sizTea Time S只要求判断是否在同一圈子但很多类似的题目会进一步问“每个圈子有多少人”。这时候如果你重新遍历一遍所有节点去数复杂度又上去了。正确做法是在并查集里维护一个sz数组初始化时sz[i] 1表示每个圈子一开始只有自己一人。在unite时如果两个根成功合并就把新根节点的sz加上旧根的szint sz[MAXN]; void unite(int a, int b) { int ra find(a); int rb find(b); if (ra rb) return; fa[ra] rb; sz[rb] sz[ra]; }这个技巧在很多涉及“连通块大小”的题目里非常实用。再配合前面的按秩合并你会发现并查集虽然代码很短但能承载的信息量相当大。5.3 从这道题延伸到Kruskal最小生成树并查集最经典的进阶应用就是最小生成树里的Kruskal算法。Kruskal的思路是把所有边按照权值从小到大排序然后依次考虑每条边如果边的两个端点已经在同一个并查集集合里说明这条边会成环跳过否则就把两个端点合并并把这边的权值加入总答案。最终就能得到连接所有节点的最小花费。这里“判断是否成环”的操作本质就是在一个动态变化的图上维护连通性和Tea Time S里“判断是否在一个朋友圈”是同一个逻辑。我曾经遇到过这样一道题给一个图每次删除一条边询问两个点是否仍然连通。很多人第一反应是用DFS或BFS判断但一旦删除操作多了就很慢。正确做法是逆向处理先把所有要删除的边删掉建立最终状态的并查集然后从最后一次删除开始反向往前推每次“删除”在逆向中就变成了“加边”直接用并查集合并即可。这类题目把并查集和逆序处理结合起来非常考察思维的灵活度。5.4 什么时候选并查集什么时候选BFS/DFS最后我再讲讲选型问题。看到一道连通性题目怎么判断是应该用并查集还是图搜索我的判断标准很简单如果题目只问你“两个点是否连通”或“整个图有多少个连通块”而且关系会不断合并、不断添加那么并查集是首选。如果你需要输出具体的路径、最短距离、方案数那么并查集无能为力必须老老实实上BFS或DFS。Tea Time S恰好落在前一类关系一次性给出查询一次性处理只需要判断连通不要求路径。所以它只用一个fa数组就足够了。很多新手把这类题想复杂总觉得朋友链需要记录下来但其实“不需要路径”本身就是并查集能高效工作的前提条件。练习并查集时我的建议是不要只顾着背模板。找一个空白小本子画出5个节点的fa数组变化过程手动模拟find和unite每一步做了什么。等你亲眼看到一次路径压缩把一条长链压成一张“菊花图”你才算真正理解了并查集的精髓。以后遇到这类题你的第一反应就不会是建图跑BFS而是顺手就敲出那十几行的并查集模板了。