You are given a simple connected undirected graph with $N$ vertices and $M$ edges. (A graph is said to be simple if it has no multi-edges and no self-loops.) A sequence $(A_1, A_2, \ldots, A_k)$ is said to be a path of length $k$ if both of the following two conditions are satisfied: An empty sequence is regarded as a path of length $0$. You are given a sting $S = s_1s_2\ldots s_N$ of length $N$ consisting of $0$ and $1$.
A path $A = (A_1, A_2, \ldots, A_k)$ is said to be a good path with respect to $S$ if the following conditions are satisfied: Under the Constraints of this problem, it can be proved that there is at least one good path with respect to $S$ of length at most $4N$.
Print a good path with respect to $S$ of length at most $4N$.Problem Statement
For $i = 1, 2, \ldots, M$, the $i$-th edge connects Vertex $u_i$ and Vertex $v_i$.
Constraints
Input
Input is given from Standard Input in the following format:
$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$ $S$
Output
Print a good path with respect to $S$ of length at most $4N$ in the following format. Specifically, the first line should contain the length $K$ of the path, and the second line should contain the elements of the path, with spaces in between.
$K$ $A_1$ $A_2$ $\ldots$ $A_K$
Sample Input 1
6 6 6 3 2 5 4 2 1 3 6 5 3 2 110001
Sample Output 1
9 2 5 6 5 6 3 1 3 6
The path $(2, 5, 6, 5, 6, 3, 1, 3, 6)$ has a length no greater than $4N$, and
- it has odd number ($1$) of $1$
- it has odd number ($1$) of $2$
- it has even number ($2$) of $3$
- it has even number ($0$) of $4$
- it has even number ($2$) of $5$
- it has odd number ($3$) of $6$
so it is a good path with respect to $S = 110001$.
Sample Input 2
3 3 3 1 3 2 1 2 000
Sample Output 2
0
An empty path $()$ is a good path with respect to $S = 000000$. Alternatively, paths like $(1, 2, 3, 1, 2, 3)$ are also accepted.
考虑序列节点相邻的在序列相邻是什么东西?欧拉环游序!
但是欧拉环游序的奇偶不一定正确,怎么办?
想一下如何改变一个位置的奇偶。可以先向他父亲走一步,然后走回来,然后再向父亲走,好像就满足了。
但是 1 没有父亲?
反正一开始都搜到了,在最后回去的时候,特判一下,不走就行了
#include<cstdio>
const int N=1e5+5;
int n,m,k,idx,a[N<<2],b[N<<2],f[N],t[N],fa[N],hd[N],e_num,u,v,c[N];
char s[N];
struct edge{
int v,nxt;
}e[N<<2];
void add_edge(int u,int v)
{
e[++e_num]=(edge){v,hd[u]};
hd[u]=e_num;
}
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
void dfs(int x,int y)
{
a[++idx]=x;
for(int i=hd[x];i;i=e[i].nxt)
{
if(e[i].v!=y)
{
dfs(e[i].v,x);
a[++idx]=x;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
if(find(u)!=find(v))
fa[find(u)]=find(v),add_edge(u,v),add_edge(v,u);
}
scanf("%s",s+1);
dfs(1,0);
for(int i=idx;i>=1;i--)
if(!t[a[i]])
t[a[i]]=1,f[i]=1;;
for(int i=1;i<idx;i++)
{
if(f[i])
if((c[a[i]]&1)==(s[a[i]]-'0'))
b[++k]=a[i],b[++k]=a[i+1],c[a[i+1]]++,c[a[i]]++;
b[++k]=a[i];
c[a[i]]++;
}
if((c[1]&1)!=(s[1]-'0'))
b[++k]=1;
printf("%d\n",k);
for(int i=1;i<=k;i++)
printf("%d ",b[i]);
}
标签:Good,number,Construct,leq,length,good,path,Path,ldots
From: https://www.cnblogs.com/mekoszc/p/17038769.html