【推导】【DFS】Codeforces Round #429 (Div. 1) B. Leha and another game about graph

题意：给你一张图，给你每个点的权值，要么是-1，要么是1，要么是0。如果是-1就不用管，否则就要删除图中的某些边，使得该点的度数 mod 2等于该点的权值。让你输出一个留边的方案。

首先如果图内有-1，那么必有解。否则如果初始不合法的点数为偶数，那么必有解，否则无解。因为删一条边，要么使图中不合法的点数+2，要么不变，要么-2。

如果有解，构造图的任意一个生成树，如果有-1，就让-1为根，否则任意结点为根。然后从叶子向根定每个点的入度数，由于自底向上，一个结点的儿子边都被处理完后，只需要决定父边是否删除即可。可以想见，根节点不用判，必然合法（前提我们已经判断其有解；如果无解，当然根节点就无法合法咯）。

实际操作时，不用构造生成树，因为DFS，用DFS树即可。

#include<cstdio>

#include<algorithm>

using namespace std;

bool vis[300005];

int v[600005],next[600005],first[300005],e,id[600005];

void AddEdge(int U,int V,int ID){

	v[++e]=V;

	id[e]=ID;

	next[e]=first[U];

	first[U]=e;

}

int n,m,d[300005],du[300005],anss[300005],ans;

bool cho[300005];

void dfs(int U,int fa,int fa_edge){

	vis[U]=1;

	int cnt=0;

	for(int i=first[U];i;i=next[i]){

		if(!vis[v[i]]){

			dfs(v[i],U,id[i]);

			if(cho[id[i]]){

				++cnt;

			}

		}

	}

	if(d[U]!=-1 && cnt%2!=d[U]){

		cho[fa_edge]=1;

		anss[++ans]=fa_edge;

	}

}

int main(){

	int x,y;

	//freopen("b.in","r",stdin);

	int fu1_node=0;

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i){

		scanf("%d",&d[i]);

		if(d[i]==-1){

			fu1_node=i;

		}

	}

	for(int i=1;i<=m;++i){

		scanf("%d%d",&x,&y);

		AddEdge(x,y,i);

		AddEdge(y,x,i);

		++du[x];

		++du[y];

	}

	int cnt=0;

	for(int i=1;i<=n;++i){

		if(d[i]!=-1 && du[i]%2!=d[i]){

			++cnt;

		}

	}

	if(fu1_node){

		dfs(fu1_node,0,0);

	}

	else if(cnt%2==0){

		dfs(1,0,0);

	}

	else{

		puts("-1");

		return 0;

	}

	sort(anss+1,anss+ans+1);

	printf("%d\n",ans);

	for(int i=1;i<ans;++i){

		printf("%d ",anss[i]);

	}

	if(ans){

		printf("%d\n",anss[ans]);

	}

	return 0;

}

巴特西

【推导】【DFS】Codeforces Round #429 (Div. 1) B. Leha and another game about graph

最新文章

热门文章