牛客网【每日一题】4月23日题目精讲边的染色

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

小团有一张n个点，m条边的无向图G，有些边上已经被标记了0或1，表示它的边权。
现在你需要给剩下的边标记边权为0或1，求有几种标记的方式满足：
对于G中任意一个环，里面所有边的边权的异或值为0。
环的定义如下：
对于任意k（k≥2）个点{a1,a2,...,ak}，若对于所有的i<k满足ai与ai+1之间有边，且a1=ak成立，则这k个点构成一个环。

输入描述:

第一行两个整数n, m。

接下来m行，每行3个整数u, v, w，表示有一条边(u,v)，若w=-1则这条边上没有标记，否则w=0或1表示这条边上标记了w。

数据保证没有重边和自环。

1≤n≤100,000 0≤m≤min(n*(n-1)/2, 100000)

输出描述:

输出方案数对998,244,353取模的值。

示例1
输入
3 3
1 2 -1
2 3 -1
3 1 -1
输出
4

题解：

看了邓老师的题解，恍然大悟，感谢大佬讲解
一下为我结合邓老师所理解的：
首先思考：一个连通图（图中任意两点都是连通的），给边标上0和1，使得任意一个环的所有边的异或和为0，问有多少种方案？

异或：相同为0，不同为1

题目要求我们给边赋值，但是边赋值很不方便，我们就看看选择给点赋值，为什么？因为边和点是共存的，特别是在一个环中，每个点都贡献了两个边，那我们就可以把这个边的值当做是边两端顶点的值的异或，一个环有m个点，m条边，异或m条边就等于将m个点都异或两次。相同为0，那么异或两次相同的值结果一定为0.那点就可以随意赋值

对于一个连通块：
将所有点的数都 ^ 1（也就是0变成1，1变成0），两点异或出来的边值并未发生改变（就相当于原本1 ^ 1 改成0 ^ 0，结果不变），n个点每个点都是有两个方案的（即0或1），那么给点赋值的方案也就是2ⁿ个，对应的边赋值方案是点的方案除以2，所以n个点的连通图有2^n-1种方案。

对于不是一个连通图：
我们可以求分散的每个连通图种类，然后乘一起就可

但是原本题目中是存在有些边一开始就赋好值，我们可以从提前标好的边开始出发找连通块，不然到最后你自己标记的很有可能和题目给你不适配，又要重新改。在存有题目给的边的这个连通块里，我们只需要确定一个点的权值，其他部分也可以因此确定。如果把这个连通块大小记作ki，那么这个连通块的存在就会使得方案数需要在原来的基础上（不考虑之前有标记）除以2 ^ki-1，因为其他点不能自由选。

还有：题目给你的数据本身可能就是矛盾，判定远直接输出0
我尽量只能理解到这份上。。

借鉴其他大佬的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 3;
const int mod = 998244353;
int f[maxn], col[maxn];
vector<pair<int,int> > edge[maxn];
bool flag;
int find(int x){
   
    return f[x] == x ? x : f[x] = find(f[x]);
}
void dfs(int u, int p){
   //染色过程
    if (!flag) return;
    for (int i = 0; i < edge[u].size(); ++i){
   
        int v = edge[u][i].first, w = edge[u][i].second;
        if (col[v] == -1){
   
            col[v] = col[u]^w;
            dfs(v, u);
        }else if (col[u]^col[v] != w){
   
            flag = 0;
			 return;
        }
    }
}
int main(void){
   
    int n, m,ans; 
  	int u, v, w;
	scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; ++i) f[i] = i;
    ans = n;
    for (int i = 1; i <= m; ++i){
   
       cin >> u >> v >> w;
        if (find(u) != find(v)){
   
            ans--;
			f[find(u)] = find(v);/
        }
        if (w != -1){
   
            edge[u].push_back(make_pair(v, w));
            edge[v].push_back(make_pair(u, w));
        }
    }
    memset(col, -1, sizeof col);
    int cnt = 0;
    flag = 1;
    for (int i = 1; i <= n; ++i){
   
        if (col[i] == -1){
   
            col[i] = 0;
			dfs(i, i);
			cnt++;
        }
    }
    if (!flag){
   
        cout << 0 << endl; 
        return 0;
    }
    ll ans = 1;
    for (int i = 0; i < cnt-ans; ++i) ans = ans*2%mod;
    cout << ans << endl;
    return 0;
}