给定\(n-1\)个\(\{1,2,...,n\}\)的子集\(E_i\)（\(E_i\ge 2\)），每个子集选择两个点连边，使得最后形成一棵树。
考虑二分图：\(u\longrightarrow id(i)(u\in E_i)\)
有解的必要条件为：删去任意节点\(u\)，形成完美匹配，结合hall定理得到\(N(S)\ge |S|+1\)
然后考虑以下方式构造，会发现这是充要条件
做法：
从\(1\)开始bfs
反复执行：令当前点为\(u\)，找到没去过且\(u\in E_i\)的\(i\)，然后跑到\(i\)集合内没有去过的点，令\(u\)为其
若走不了了，则不符合\(N(S)\ge |S|+1\)
另外，若用dfs也可以，要等全部走一遍再判非法
原文：https://www.cnblogs.com/Grice/p/12952005.html