自动搬运

查看原文

来自洛谷，原作者为

	3493441984zz **

搬运于2025-08-24 21:44:29，当前版本为作者最后更新于2019-02-02 10:53:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

动态规划？（我不会）

直接找规律搜索!!!

题外话:

可能本人的思路跟楼下们相同，反正我看不懂$qwq$（本人很菜）

所以我就自己琢磨，然后希望能表述清楚，我做完后偷瞄了楼下$dalao$们的代码，好像差不多$qwq$（尴尬）

思路：

这道题目不难，我也不知道怎么用$dp$做$qwq$

先说做法（至于为什么下文会提到）：

我们搜索每一个没访问过的点，对于搜索进来的这条边，我们不管它，让它继续搜索下去，直到访问了每个节点后，统计度数，如果现在是偶数度的话，我们就连上最开始搜索进来的边，保证当前点是奇数度

知道你们现在还迷糊$qwq$，来人啊，上性质!!!

于是我门开始找性质：

$1$、只需要一条边的变化，就能从奇数度与偶数度相互转换（废话）

也就是说一个点如果多一条边或者少一条边，就能从奇数度变为偶数度，或者从偶数度变为奇数度（感觉我在侮辱你们智商）

那么，来人啊!上样例!!!

$\quad1-2$

$\,\,\quad$$\quad $/

$\quad\quad3-4$

我们从$1$号出发，搜索到$2$节点，继续搜索到$3$号节点，$3$号节点不能去$1$号，因为$1$被访问过了，所以到$4$去，而$4$号节点没有能走的地方了，于是我们统计$4$号点的度数为$0$（不算$3-4$这条搜索进来的边），那么现在$4$号节点就是偶数度，那么我们只能通过连上搜索进来的这条边$3-4$来保证$4$号点是奇数度

于是保留$3-4$这条边，那么返回到$3$节点，$3$节点相邻的$1,2,4$都被访问过了，于是统计度数，因为不算$2-3$这条边，所以$3$的度数为$1$，因为与$4$连了一条边，而现在是奇数度，所以我们不能连上$2-3$这条边，不然就多此一举的从奇数度变为了偶数度

那么又返回到$2$节点，与之相邻的点也都被访问过了，那么统计度数，由于$1-2$这条搜索进来的边先不管，而$2-3$这条边不连，所以$2$号点的度数为$0$，那么我们就必须连上$1-2$这条搜索进来的边来保证当前点是奇数度

于是保留$1-2$这条边，返回到$1$节点，发现没有与之相邻没访问过的点了，那么统计度数为$1$，因为与$2$连了边，那么也就方案成立了，所有点的度数都是奇数度啦

所以我们就连了$1-2$,$3-4$保证所有点是奇数度

等等？？样例输出不是这样啊？？

不是有苏卿念$dalao$提供的$SPJ$嘛

那么样例输出是怎么来的呢？？

其实是访问的顺序不一样导致的，那就再模拟一遍吧$qwq$

$\quad1-2$

$\,\,\quad$$\quad $/

$\quad\quad3-4$

我们还是从$1$号点开始搜索，这次我们不先去$2$号点，而是去$3$号点，那么到了$3$号点后，我们随便往哪走，就先往$2$走吧，到了$2$号点后，发现不能走了，并且度数为$0$，那么就必须连上$3-2$这条边，返回到$3$节点，搜索到$4$号点，发现不能走了，于是统计度数为$0$，于是必须连上$3-4$这条边，返回到$3$节点后，发现不能走了，统计度数为$2$，那么就必须连上$1-3$，保证当前点是奇数度，那么返回到$1$节点，统计度数为$1$，于是完美结束

那么保留的边就是$1-3,2-3,3-4$啦

记得连边连双向边

最后到了美滋滋的代码时间~~~

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 50007
#define M 100007
using namespace std;
struct Edge
{
	int to,nxt,id;
}edge[M<<1];
int n,m,cnt;
int head[N],ans[M];
bool vis[N];
void Add(int u,int v,int id)
{
	edge[++cnt]=(Edge){v,head[u],id};
	head[u]=cnt;
}
bool Dfs(int u)
{
	vis[u]=1;
	int du=0;
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(vis[v])
			continue;
		if(Dfs(v))
		{
			++du;
			ans[++cnt]=edge[i].id;
		}
	}
	if(du%2==0)
		return 1;
	else
		return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		Add(u,v,i);
		Add(v,u,i);
	}
	cnt=0;
	for(int i=1;i<=n;++i)
		if(!vis[i])
			if(Dfs(i))
			{
				printf("-1");
				return 0;
			}
	sort(ans+1,ans+1+cnt);
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;++i)
		printf("%d\n",ans[i]);
}