AGC029F Construction of a tree

题意：给定 个点集（全集为 ），从每个集合内选两个点连边，使得最后形成一棵树。或指出无解。

，集合总大小 ，时限 。

---

设给出的 个集合为 。

选出一个子集族 ，定义 为 中所有集合的并集。

若 则必然连成环，无解。

若有解，所有 。

这很类似 定理（比其更强），尝试构造二分图。

---

为每个集合 构造一个左侧点 ，向所有 中的点连边。

求出该二分图的一个匹配。若不存在完备匹配显然无解。

若存在完备匹配，则右侧恰有一个点 没有被匹配到。

从 开始 dfs，找一个未使用的相邻左侧点（代表集合），然后找出其匹配点 ，该集合选择的边即为 。

然后从 开始继续 dfs 构造。若不能完整遍历，则无解。

证明：考虑何时不能继续 dfs：对于所有被经过的右侧点，其相邻的左侧点都被经过了。

经过 个右侧点则会经过 个左侧点。

考虑所有未被经过的左侧点，其邻点也只能是未被经过的右侧点，尴尬的是，此时右侧点和左侧点一样多。

所以，显然违反了 ，无解。

使用 计算二分图匹配，复杂度 。