1集合划分ADT
闭卷重建集合划分ADT的ADT、表示不变量、操作与复杂度。
数据结构与抽象数据类型 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2父指针森林与朴素退化
闭卷重建父指针森林与朴素退化的ADT、表示不变量、操作与复杂度。
3路径压缩
闭卷重建路径压缩的ADT、表示不变量、操作与复杂度。
4按秩/大小合并
闭卷重建按秩/大小合并的ADT、表示不变量、操作与复杂度。
5近常数均摊与α(n)
闭卷重建近常数均摊与α(n)的ADT、表示不变量、操作与复杂度。
6Kruskal与环检测
闭卷重建Kruskal与环检测的ADT、表示不变量、操作与复杂度。
7实验：DSU与Kruskal
闭卷重建实验：DSU与Kruskal的ADT、表示不变量、操作与复杂度。
第 1 页 · 背面（答案）
机制：每个根parent指自己，非根沿父链到根；任意连接可能形成长链；实验：构造最坏链并测find路径长度；边界：union若不先find两个根会把内部节点相连甚至制造环。
机制：makeSet建立单元素集合，find返回代表元，union合并两个集合；代表元身份可变但同集合关系稳定；实验：对一串union/find输出分量数量与代表关系；边界：调用者不能依赖某个具体根永远是代表，union同集合也不应减少计数。
机制：把小树挂到大树或低秩挂高秩，限制高度；同秩合并才增加新根秩；实验：逐union记录size/rank和最大深度；边界：rank是高度上界而非当前精确高度，路径压缩后通常不下调rank。
机制：find回溯时把路径节点直接接根，后续查询显著变短且不改变集合划分；实验：对长链执行一次find并输出压缩前后parent；边界：递归版在极深链上可能栈溢出，迭代压缩需保存遍历路径。
机制：边按权重递增，若两端不在同一分量就选边并union，得到最小生成森林；实验：对带相同权边图执行稳定排序并输出所选边与总权；边界：图不连通时得到森林而非单树，负权允许，平行边也需正确处理。
机制：路径压缩配按秩让m次操作总成本O(mα(n))，α增长极慢但并非数学常数；实验：比较朴素、只按大小和两者结合在对抗序列的父链访问数；边界：不能把α(n)证明简化成“树高度一直1”，单次首次find仍可能走多步。
机制：实现迭代find压缩、按大小union、componentCount和Kruskal；实验：覆盖重复union、长链压缩、非连通、平行边和相同权测试；边界：Kruskal排序键和顶点范围要固定，不能用BFS连通检查替代DSU核心。