首页 > 代码库 > Codeforces 453C Little Pony and Summer Sun Celebration(构造)
Codeforces 453C Little Pony and Summer Sun Celebration(构造)
题目链接:Codeforces 453 Little Pony and Summer Sun Celebration
题目大意:n个节点,m条边,然后m行给定边,最后一行表示每个节点需要进过的次数为奇数次还是偶数次。
解题思路:构造,任意从一个奇数点开始(统一森林的处理),然后每次向下遍历没有经过的节点,并且回溯,每次回溯都要判断一下刚才走过的点满不满足条件,不满足的话就再走一次。最后对于根节点,最后一次回溯要不要走根据当前走过的次数决定。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
int N, M, a, b, s;
int ans, rec[maxn*4];
int c[maxn], v[maxn];
vector<int> g[maxn];
void init () {
ans = s = 0;
scanf("%d%d", &N, &M);
memset(v, 0, sizeof(v));
for (int i = 0; i < M; i++) {
scanf("%d%d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= N; i++) {
scanf("%d", &c[i]);
if (c[i])
s = i;
}
}
inline void set (int u) {
c[u] ^= 1;
rec[ans++] = u;
}
void dfs (int u) {
set(u);
v[u] = 1;
for (int i = 0; i < g[u].size(); i++) {
if (v[g[u][i]])
continue;
dfs(g[u][i]);
set(u);
if (c[g[u][i]]) {
set(g[u][i]);
set(u);
}
}
}
bool judge () {
for (int i = 1; i <= N; i++)
if (c[i])
return false;
return true;
}
int main () {
init();
dfs(s);
if (c[s]) {
c[s] = 0;
ans--;
}
if (judge ()) {
printf("%d\n", ans);
if (ans) {
printf("%d", rec[0]);
for (int i = 1; i < ans; i++)
printf(" %d", rec[i]);
printf("\n");
}
} else
printf("-1\n");
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。