二分图判定 没啥技巧，最难的是把图论模型建起来。 luogu1330 封锁阳光大学 相邻两个点只能封锁一个，但是要覆盖所有边。对应到二分图上就是左部右部点的数量取较小值。 图可能不连通，取的是每一张二分图的左右边的较小值。 #include<bits/stdc++.h> using namespace std; #define int …

并查集是一个森林，每棵树表示一个集合，并且这个集合根据某种具有传递性的关系构建起来。 普通并查集关心的信息只有 $x$ 所在集合的根，$fa_x$ 表示的仅仅是一个传递性关系，即 $fa_x$ 与 $x$ 所在集合的根相同。从任意节点往上跳，都能找到它所在集合的根。 使用路径压缩优化，在向上访问节点时，把路径上所有节点的 $fa$ 都改为根，那么就…