[ABC244G] Construct Good Path

标签：Good number Construct leq length good path Path ldots

Problem Statement

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.)
For $i = 1, 2, \ldots, M$, the $i$-th edge connects Vertex $u_i$ and Vertex $v_i$.

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:

For all $i = 1, 2, \dots, k$, it holds that $1 \leq A_i \leq N$.
For all $i = 1, 2, \ldots, k-1$, Vertex $A_i$ and Vertex $A_{i+1}$ are directly connected with an edge.

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:

For all $i = 1, 2, \ldots, N$, it holds that:
- if $s_i = 0$, then $A$ has even number of $i$'s.
- if $s_i = 1$, then $A$ has odd number of $i$'s.

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$.

Constraints

$2 \leq N \leq 10^5$
$N-1 \leq M \leq \min\lbrace 2 \times 10^5, \frac{N(N-1)}{2}\rbrace$
$1 \leq u_i, v_i \leq N$
The given graph is simple and connected.
$N, M, u_i$, and $v_i$ are integers.
$S$ is a string of length $N$ consisting of $0$ and $1$.

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

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

Sample Output 2

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