【AtCoder Grand 029F】Construction of a tree 题解

题目大意

  设全集为 $\{1,2,\cdots,n\}$，给出 $n-1$ 个子集 $E_1,\cdots,E_{n-1}$，$|E_i| \ge 2$，请从每个子集中选出两个元素，视为给两个节点连一条边，使得最后构成一棵树。
  输出一种方案或是“-1”表示无解。

  $n \leq 10^5,\ \ \sum |E_i| \le 2 \times 10^5$
  4s

$$\\$$ $$\\$$ $$\\$$

题解

  这种觉得好像是流但看上去不是很能流最后又确实是流的题真的一流。。。

  考虑必要条件，一棵树去掉根以后，边和点可以一一对应（每个点跟它连向父亲的边对应），因此建一个二分图，左边是 $1,\cdots,n$ 表示节点，右边是 $E_1,\cdots,E_{n-1}$ 表示边，那么左边去掉根节点之后应当有完美匹配。并且这是一棵无根树，所以左边去掉任意点以后都应当有完美匹配。
  然后看看这个条件充不充分。有完美匹配以后我们还需要的是整个图连通，也就是根节点可以到达其他所有点，也就是从左边的根节点开始，沿着“非匹配边-匹配边-非匹配边-……”的交错路能遍历所有的点。题解证明了这是成立的：因为“左边去掉任意点以后都有完美匹配”，所以任取非根节点 $x$，把去掉它的完美匹配与去掉根的完美匹配并起来，这样除了根和 $x$ 外所有点的度数都是 $2$（因为每个点都连了两条匹配边，只有根和 $x$ 连了一条匹配边）。现在全图只有根和 $x$ 度数为 $1$，那它们必然在同一个连通块里，因为连通块的总度数一定是偶数。所以根和 $x$ 是连通的。
  因此，“有解” $\to$ “左边去掉任意点都有完美匹配” $\to$ “任意求一个完美匹配，从左边的根节点开始，沿‘非匹配边-匹配边-非匹配边-……’做 BFS，可以遍历所有的点”，并且这样也就构造出一组解了。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=1e5+5, maxsum=2e5+5, maxe=4e5+5;

int n,m;
vector<int> S[maxn];

vector<int> e[maxn];
int dis[2*maxn],pt[2*maxn],maxdis;
bool Hopcroft_bfs() {
	memset(dis,255,sizeof(dis));
	maxdis=-1;
	queue<int> Q;
	fo(i,1,n) if (!pt[i]) {
		Q.push(i);
		dis[i]=0;
	}
	while (!Q.empty()) {
		int cur=Q.front(); Q.pop();
		for(int go:e[cur]) if (dis[go]==-1) {
			dis[go]=dis[cur]+1;
			if (!pt[go]) {
				maxdis=dis[go];
				continue;
			} else {
				dis[pt[go]]=dis[go]+1;
				Q.push(pt[go]);
			}
		}
	}
	return maxdis>-1;
}
bool Hopcroft_dfs(int k) {
	for(int go:e[k]) if (dis[k]+1==dis[go]) {
		dis[go]=-1;
		if (!pt[go] || Hopcroft_dfs(pt[go])) {
			pt[k]=go, pt[go]=k;
			return 1;
		}
	}
	return 0;
}
int Hopcroft() {
	int re=0;
	while (Hopcroft_bfs())
		fo(i,1,n) if (!pt[i]) re+=Hopcroft_dfs(i);
	return re;
}

bool vis[maxn];
pair<int,int> ans[maxn];
int main() {
	scanf("%d",&n);
	fo(i,1,n-1) {
		int sz,x;
		scanf("%d",&sz);
		fo(j,1,sz) {
			scanf("%d",&x);
			e[x].push_back(n+i);
			S[x].push_back(i);
		}
	}
	
	if (Hopcroft()!=n-1) {puts("-1"); return 0;}
	
	int root;
	fo(i,1,n) if (!pt[i]) {root=i; break;}
	queue<pair<int,int>> Q;
	for(int x:S[root]) {
		vis[x]=1;
		Q.push(make_pair(root,x));
	}
	while (!Q.empty()) {
		auto cur=Q.front(); Q.pop();
		int son=pt[n+cur.second];
		ans[cur.second]=make_pair(cur.first,son);
		for(int x:S[son]) if (!vis[x]) {
			vis[x]=1;
			Q.push(make_pair(son,x));
		}
	}
	
	fo(i,1,n-1) if (!vis[i]) {puts("-1"); return 0;}
	fo(i,1,n-1) printf("%d %d\n",ans[i].first,ans[i].second);
}