Codeforces Contest 840 B Leha and another game about graph —— dfs

This way

题意：

给你一张图，无自环，有重边。每个点都有一个值，0,1，-1，0是要求这个点连的边有偶数个，包括0,1表示这个点连的边有奇数个，-1表示无要求，之后给你m条边，最后问你留下哪些边可以满足要求。

题解：

很明显可以看出来，当有奇数个1且没有-1的时候是不可能的，因为要满足奇数条边连向一个点，那么只有使得奇数的点两两相连，最后悔剩下一个奇数的点，这个点无论怎么练都会破坏其它点的关系。
那么由于它是连通图，当它有偶数个1的时候是必然能够所有1两两相连的，如果有奇数个1和若干个-1，只需要使得其中的一个-1变成1即可。那么怎么连？我们肯定是要连两个1使得这两个1之后不在任何的两个1中间：

如果我们开始的时候连了中间的两个1了，那么之后就不好连，如果硬做的话肯定是会t的。那么我们怎么找最旁边的两个1？我们用一个vis数组记录当前访问了那些点，之后就不会再访问，也就是当成一棵树来做。最后一个1 returen的是1，回溯的时候改变当前点的值，也就是异或=1，那么到下一个1了他的值就变成0，然后返回的就是0.返回1的时候我们直接加入答案，因为只有一个1的话肯定是要找到另一个点，并且dfs下去找不到点了，所以肯定是在别的地方，这样就做完了。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
struct node
{int to,next,id;
}e[N*2];
int cnt,head[N];
void add(int x,int y,int id)
{e[cnt].to=y;e[cnt].next=head[x];e[cnt].id=id;head[x]=cnt++;
}
int a[N],vis[N];
vector<int>ans;
int dfs(int x,int fa)
{vis[x]=1;for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne==fa||vis[ne])continue;int aa=dfs(ne,x);if(aa)ans.push_back(e[i].id),a[x]^=1;}return a[x];
}
int main()
{memset(head,-1,sizeof(head));int n,m;scanf("%d%d",&n,&m);int sta=0,neg=0,odd=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]==1)sta=sta?sta:i,odd++;if(a[i]==-1)neg=neg?neg:i;}int x,y;for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),add(x,y,i),add(y,x,i);if(odd%2&&!neg)return 0*printf("-1\n");neg=odd%2?neg:0;for(int i=1;i<=n;i++)if(a[i]==-1)a[i]=i==neg?1:0;if(sta)dfs(sta,0);printf("%d\n",ans.size());for(int i=0;i<ans.size();i++)printf("%d\n",ans[i]);return 0;
}