欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CodeForces - 453C Little Pony and Summer Sun Celebration

程序员文章站 2022-06-27 17:12:16
博主的 BiBi 时间小马宝莉。。。在博主的少年时代是博主即使不做作业也要看的动画片。然而,还是没有读对题。Description图可能有几个连通块。不能从每个连通块重新开始。Solution其实思路很新奇。把图化成树。如果儿子的奇偶性不对,就走到父亲再回来。父亲同理。对于根节点没有爸爸,可以通过最后是否停在根节点来改变奇偶性。关于根节点的选取,我们尽量选择 aaa 值为 111 的。因为可能只有一个 111,但是不与外界相连的情况。Code#include

博主的 BiBi 时间

小马宝莉。。。在博主的少年时代是博主即使不做作业也要看的动画片。

然而,还是没有读对题。

Description

  • 图可能有几个连通块。
  • 不能从每个连通块重新开始。

Solution

其实思路很新奇。

把图化成树。如果儿子的奇偶性不对,就走到父亲再回来。父亲同理。

对于根节点没有爸爸,可以通过最后是否停在根节点来改变奇偶性。

关于根节点的选取,我们尽量选择 aa 值为 11 的。因为可能只有一个 11,但是不与外界相连的情况。

Code

#include <cstdio>
#include <vector>
using namespace std;

const int N = 1e5 + 5;

int n, m, a[N], s[N];
bool vis[N];
vector <int> e[N], ans;

int read() {
	int x = 0, f = 1; char s;
	while((s = getchar()) > '9' || s < '0') if(s == '-') f = -1;
	while(s >= '0' && s <= '9') x = (x << 1) + (x << 3) + (s ^ 48), s = getchar();
	return x * f;
}

void dfs(const int u, const int root, const int fa) {
	ans.push_back(u); s[u] = 1; vis[u] = 1;
	for(int i = 0; i < e[u].size(); ++ i) {
		int v = e[u][i];
		if(vis[v]) continue;
		dfs(v, root, u);
	}
	if(u == root && s[u] != a[u]) {
		ans.pop_back(); s[u] ^= 1;
		return;
	}
	if(u == root) return;
	if(s[u] != a[u]) {
		ans.push_back(fa); ans.push_back(u);
		s[u] ^= 1; s[fa] ^= 1;
	} 
	ans.push_back(fa); s[fa] ^= 1;
}

bool ok() {
	for(int i = 1; i <= n; ++ i) if(s[i] != a[i]) return 0;
	return 1;
}

int main() {
	int u, v;
	n = read(), m = read();
	for(int i = 1; i <= m; ++ i) {
		u = read(), v = read();
		e[u].push_back(v); e[v].push_back(u);
	}
	for(int i = 1; i <= n; ++ i) a[i] = read();
	int start = 1;
	for(int i = 1; i <= n; ++ i)
		if(a[i] == 1) start = i;
	dfs(start, start, 0);
	if(! ok()) return puts("-1"), 0;
	printf("%d\n", ans.size());
	for(int i = 0; i < ans.size(); ++ i) printf("%d ", ans[i]);
	return 0;
}

本文地址:https://blog.csdn.net/LBCLZMB/article/details/107622438

相关标签: 搜索