牛客 边的染色

边的染色

边的染色

题目大意

给一个无向图，边权是0或1，其中一些边上的边权没有给出，要给那些没有边权的边赋值（0或1）使得图上的环中的边权异或下来为0，问有多少种方法.

题解

我想不出来，，我太菜了，害
把边上的边权变成点权，使得这条边端点的点权异或值等于边权，
因为这样的话环上的边就可以表示为(v1^v2) (v2^v3) (v3^v4) (v4^v1)这种的
然后边权异或和就是0了。。
然后 看没确定边权的边对答案的贡献
如果左右两个点在同一个连通块的话这条边得边权确定了 就是两个点的点权异或。
如果不在的话，答案就乘2，这条边可以是0也可以是1。
所以 就是先按有边权的建个图，看一下这些边矛不矛盾，矛盾的话答案就是0，不矛盾的话就把其他的边加到图中 看这个边的端点是不是在同一个连通图里，这个可以用并查集实现。

代码

 #include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <set>
#include <queue>
#include <string>
#include <iostream>
#include <stack>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
std::vector<pii> vv[maxn];
int f = 1;
int vis[maxn];
int val[maxn];
int fa[maxn];
int temp = 0;
void dfs(int x)
{
   
	fa[x] = temp;
	if(f == 0)
		return;
	for(int  i= 0; i < vv[x].size(); i ++ )
	{
   
		pii t = vv[x][i];
		int v = t.first;
		if(vis[v])
		{
   
			if((val[v] ^ val[x]) != t.second)
			{
   
				f = 0;
				return;
			}
			continue;
		}
		vis[v] = 1;
		val[v] = val[x] ^ t.second;
		dfs(v);
	}
}
pii pp[maxn];

int findx(int x)
{
   
	return fa[x] == x ? x : fa[x] = findx(fa[x]);
}

int main()
{
   
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i ++ )
		fa[i] = i;
	for (int i = 1; i <= m; i ++ )
	{
   
		int x,y,val;
		scanf("%d%d%d",&x,&y,&val);
		if(val == -1)
		{
   
			pp[i].first = x;
			pp[i].second = y;
			continue;
		}
		vv[x].push_back(make_pair(y,val));
		vv[y].push_back(make_pair(x,val));
	}
	for (int i = 1; i <= n; i ++ )
	{
   
		if(vis[i] == 0)
		{
   
			vis[i] = 1;
			temp = i;
			val[i] = 1;
			dfs(i);
		}
	}
	if(f == 0)
	{
   
		printf("%d\n",0);
		return 0;
	}
	ll ans =  1;
	for (int i = 1; i <= m; i ++ )
	{
   
		int x = pp[i].first;
		int y = pp[i].second;
		int xx = findx(x);
		int yy = findx(y);
		if(xx == yy)
		{
   
			continue;
		}
		ans = ans * 2 % mod;
		fa[xx] = yy;
	}
	printf("%lld\n",ans);
}