【链接】点击打开链接
【题意】
给出一个连通图，并给每个点赋一个d值0或1或-1,要求选出一个边的集合，使得所有的点i要么d[i] == -1,要么 dgree[i] % 2 == d[i]，dgree[i]代表i结点的度数。
【题解】
先统计出所有点所要求的度数的和cnt1。(不考虑-1);
这里的cnt1的奇偶性也就是最后的图的所有点的度数和的奇偶性.
显然只要是一张图,它的所有的度数的和就必须为偶数。
所以,如果cnt1是个奇数,且没有为-1的点,那么直接输出-1就好,无解.
如果有-1的话,那么显然我们是可以把它凑成偶数的。
这样把所有的-1都改成0或1,然后满足n个点的度数和为偶数就好了。
度数和为偶数之后,我们从任意一个点开始进行dfs.
我们可以考虑它任意的一个生成树。(其他地方不加边)
(不加任何边也算是偶数!)
然后从树的叶子节点往上处理。
(我们接下来的任务就是维护所有节点的度数之和总为偶数)
对于当前节点cur.
如果d[cur]==0,则跳过cur和parent[cur]之间的边.不做处理,则度数之和不变还是偶数.
如果d[cur]==1,则把cur和parent[cur]之间的边加到ans里面去,同时把d[parent[cur]]取反,也即0变成1,1变成0,然后d[cur]变成0.这样做,我们把d[cur]的奇偶性变了一下,然后d[parent[cur]]的奇偶性也变了.则度数之和的奇偶性还是不变,仍然为偶数。同时d[cur]变为0,表示cur这个点不需要边了,然后d[cur的父节点]的奇偶性改变的话,表示cur的父亲节点需不需要边的状态也改变了。
我们最后的目标,显然是让所有的d[cur]都变成0,也即所有的点都不需要边了。
而我们的操作能时刻保证,所有的d值的和都为偶数,则根节点进行操作完之后,所有d的值的和仍然为偶数。
而根节点以下的所有点的值都变成了0,根节点的d值为0或为1，那么也就是说根节点的d值也变成了0。
这就说明可以让所有的d值都为0.
输出加入的边就好。
【错的次数】
0
【反思】
图的点的度数之和总是一个偶数的。
用生成树来简化图的问题。
只要度数之和为偶数.(只要求每个点的度数的奇偶性)那么一定有解。
【代码】
/*
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <cstdlib>
#include <cmath>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define ld long double
#define ms(x,y) memset(x,y,sizeof x)
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rs(x) scanf("%s",x)
#define rf(x) scnaf("%lf",&x)
#define oi(x) printf("%d",x)
#define ol(x) printf("%lld",x)
#define oc putchar(' ')
#define os(x) printf(x)
#define all(x) x.begin(),x.end()
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
#define sz(x) ((int) x.size())
#define ld long double
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
//mt19937 myrand(time(0));
//int get_rand(int n){return myrand()%n + 1;}
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 3e5;
int n, m,d[N+10],cnt1,cnt0;
bool bo[N + 10];
vector <pii> g[N + 10];
vector <int> ans;
void dfs(int x) {
bo[x] = true;
for (pii temp : g[x]) {
int y = temp.first, id = temp.second;
if (!bo[y]) {
dfs(y);
if (d[y] == 1) {
d[x] ^= 1;
d[y] = 0;
ans.pb(id);
}
}
}
}
int main() {
//Open();
//Close();
ri(n), ri(m);
rep1(i, 1, n) {
ri(d[i]);
if (d[i] == 1) cnt1++;
if (d[i] == -1) cnt0++;
}
rep1(i, 1, m) {
int x, y;
ri(x), ri(y);
g[x].pb(mp(y,i)), g[y].pb(mp(x,i));
}
if ((cnt1 & 1) && cnt0 == 0) {
puts("-1");
return 0;
}
cnt1 = cnt1 & 1;
rep1(i,1,n)
if (d[i] == -1) {
d[i] = cnt1;
cnt1 = 0;
}
dfs(1);
oi(sz(ans)); puts("");
for (int x : ans)
oi(x), puts("");
return 0;
}