自动搬运

查看原文

来自洛谷，原作者为

	TianyiLemon 我真是个笨蛋。

搬运于2025-08-24 22:35:56，当前版本为作者最后更新于2022-02-04 20:43:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有趣的题。

碰到这种二元关系的题，我们通常可以考虑从图论的角度去思考。

具体地说，我们把麦片当作点，把奶牛当作边。

我一开始考虑把奶牛当作有向边，从第一喜欢的麦片指向第二喜欢的麦片，但是有向图没有什么好的性质。

所以我们不妨把奶牛看作无向边，再考虑它是否满足题目条件。

考虑每个连通块，设连通块内能够吃到麦片的奶牛数为 $cnt$，连通块点数为 $n$，边数为 $m$。

显然 $cnt\le \min(n,m)$。

通过手玩几组数据，我们不妨大胆猜想 $cnt= \min(n,m)$。

具体地说，如果 $m=n-1$，即连通块是一棵树，则 $cnt=n-1$；否则 $cnt=n$。

接下来我们考虑如何构造。

1. $m=n-1$：

   从连通块内任意一个节点开始 bfs/dfs，按照 bfs/dfs 顺序输出边即可。

   正确性说明：

   设一条边为 $(u,v)$，其中 $u$ 是 $v$ 在树上的祖先。

   在访问到这条边的时候，$v$ 一定没有被选择，$u$ 可能被选可能不被选。

   所以不论这条边的指向如何，它都一定能够被满足。

   所以恰好有 $m=n-1$ 条边被满足，方案是正确的。

2. $m\ge n$：

   我们考虑建出连通块的一棵搜索树，这时候我们还要使得连通块内的一条后向边（即不在搜索树上的边）被满足。

   所以我们不妨先输出一条后向边，设这时被选择的点（即第一喜欢的麦片）为 $s$。

   以 $s$ 为根对搜索树进行 bfs/dfs，按照顺序输出树上的边。

   最后再输出不能被满足的边即可。

   正确性说明：

   依然考虑边 $(u,v)$，其中 $u$ 是 $v$ 在树上的祖先。

   如果 $u=s$，显然只能选择 $v$。

   否则按照数学归纳法，$u$ 一定已经被选择，所以不论 $v$ 是不是第一选择，都只能选择 $v$。

   这时有恰好 $n$ 条边被满足，方案是正确的。

时间复杂度为 $O(n+m)$。

#include<bits/stdc++.h>
#define N 100009
using namespace std;
int n,m,ans,hd[N],tot,fi[N],c[N],nV[N],nE[N],nC,choose[N];
bool in[N<<1],vst[N];//in代表在不在搜索树内,vst代表有没有被选
struct edge{
	int t,nxt;
} es[N<<1];
//编号为i的边为(i*2)和(i*2+1)
void add(int u,int v){es[++tot]=(edge){v,hd[u]},hd[u]=tot;}
void dfs(int u){
	++nV[c[u]];
	for(int i=hd[u];i;i=es[i].nxt){
		++nE[c[u]];
		int v=es[i].t;
		if(c[v])continue;
		in[i]=in[i^1]=1;
		c[v]=c[u];
		dfs(v);
	}
}
void print(int u,int in_edge){
	for(int i=hd[u];i;i=es[i].nxt)if(in[i]&&i!=(in_edge^1)){
		printf("%d\n",i>>1);vst[i>>1]=1;
		print(es[i].t,i);
	}
}
int main(){
	cin>>n>>m;
	tot=1;
	for(int i=1;i<=n;++i){
		int u,v;scanf("%d%d",&u,&v);fi[i]=u;
		add(u,v),add(v,u);
	}
	for(int i=1;i<=m;++i)
		if(!c[i]){
			c[i]=++nC;
			dfs(i);
		}
	for(int i=1;i<=n;++i)if(!in[i<<1]){//第二种情况(选择一条后向边)
		int id=c[es[i<<1].t];choose[id]=i;
	}
	for(int i=1;i<=m;++i)if(nE[c[i]]==nV[c[i]]*2-2)
		choose[c[i]]=i;//第一种情况（dfs起始点）
	ans=m;
	for(int i=1;i<=nC;++i)
		if(nE[i]==nV[i]*2-2)--ans;
	cout<<n-ans<<endl;
	for(int i=1;i<=nC;++i){
		if(nE[i]==nV[i]*2-2){
			print(choose[i],0);
		}else{
			printf("%d\n",choose[i]);vst[choose[i]]=1;
			print(fi[choose[i]],0);
		}
	}
	for(int i=1;i<=n;++i)
		if(!vst[i])printf("%d\n",i);
	return 0;
}