文章目录
- 一.题目
- 二.题解思路
- 三.Code
- 谢谢！
一.题目
传送门
题意翻译：
给一个无向图，n个点m条边，给定一个01序列，如果a[i]=1，要求走到这个点奇数次，否则，要求走到这个点偶数次，请你任选起点，输出满足要求的经过点的序列和序列长度，序列长度不能超过4n。
二.题解思路
首先都说了这是一道有技术的搜索， 所以我们先从原图中提取出一颗树。
如果整张图不连通，若几个不连通的图里有两个及以上的图有要求遍历基数次的点，就无解。
若是连通图，那么开始遍历这棵树。遍历到一个节点，回溯时若该节点的遍历次数不满足要求，那么就走到它的父亲节点在走到它，它的奇偶性就被改变了，虽然他的父亲节点的奇偶性也被改变了，但是当它的父亲节点回溯时，又像这样处理就行了。这时就有一个问题，如果根节点遍历的奇偶性不对怎么办？很简单。你直接最后一次遍历时退回去，最后一次不遍历根节点就行了。
三.Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;#define M 100005vector <int> G[M];
int n, m, st, x[M], cnt, ans[M * 4], now[M];
bool vis[M];void dfs (int Index, int fa){vis[Index] = 1;ans[++ cnt] = Index;now[Index] ^= 1;for (int i = 0; i < G[Index].size (); i ++){int tmp = G[Index][i];if (! vis[tmp]){dfs (tmp, Index);now[Index] ^= 1;ans[++ cnt] = Index;}}if (now[Index] != x[Index]){ans[++ cnt] = fa;ans[++ cnt] = Index;now[fa] ^= 1;now[Index] ^= 1;}
}
int main (){scanf ("%d %d", &n, &m);for (int i = 1; i <= m; i ++){int u, v;scanf ("%d %d", &u, &v);G[u].push_back (v);G[v].push_back (u);}for (int i = 1; i <= n; i ++){scanf ("%d", &x[i]);if (x[i])st = i;}dfs (st, 0);for (int i = 1; i <= n; i ++){if (! vis[i] && x[i]){printf ("-1\n");return 0;}}if (cnt > 1 && ans[cnt - 1] == 0)cnt -= 3;printf ("%d\n", cnt);for (int i = 1; i <= cnt; i ++)printf ("%d ", ans[i]);return 0;
}