Leha and another game about graph
题目大意:给你一个图,每个节点都有一个v( -1 , 0 ,1)值,要求你选一些边,使v值为1
的点度数为奇数,v值为0的度数为偶数,v值为-1的节点没有限制。让你输出边的集合,
如果不存在这样的边集,输出-1。
写的时候没啥思路,dfs瞎搞了一下过不了。
思路:我们先考虑没有解的情况,如果v值为1的点为奇数个,且没有v为-1的点,则不存在
解,因为你添加一条边改变了两个v值非-1点的奇偶性,又有奇数个v值为1的点,不可能满足
全部点,所以不存在解。然后我们把当前节点只和它的父节点联系在一起,如果当前节点
不满足条件,就加上它和它父节点之间的那条边,这里如果有v位-1的点,我们优先用它作为
根节点,因为子节点必定满足了条件,只要看根节点就行了。
#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define mk make_pair #define pii pair<int,int> #define pb push_back using namespace std; const int N=3*1e5+5; int v[N],n,m; vector<pii> e[N]; vector<int> ans; bool vis[N],e_vis[N]; void dfs(int u,int e_id) {vis[u]=true;bool flag=false;int len=e[u].size();for(int i=0;i<e[u].size();i++){pii p=e[u][i];if(vis[p.fi]) continue;dfs(p.fi,p.se);if(e_vis[p.se]) flag=!flag;}if(v[u]==-1 || flag==v[u]) return;if(e_id!=-1){e_vis[e_id]=true;ans.pb(e_id);} } int main() {cin>>n>>m;int st=-1,sum=0;for(int i=1;i<=n;i++){scanf("%d",&v[i]);if(st==-1 && v[i]==-1) st=i;if(v[i]!=-1) sum+=v[i];}for(int i=1;i<=m;i++){int f,t; scanf("%d%d",&f,&t);e[f].pb(mk(t,i));e[t].pb(mk(f,i));}//cout<<st<<endl;if(st==-1 && sum&1){puts("-1");return 0;}if(st==-1) dfs(1,-1);else dfs(st,-1);int len=ans.size();sort(ans.begin(),ans.end());printf("%d\n",len);for(int i=0;i<len;i++) printf("%d\n",ans[i]);return 0; }