链接：

时间限制：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^n^个，对应的边赋值方案是点的方案除以2，所以n个点的连通图有2^n-1^种方案。

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

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

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

借鉴其他大佬的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
const int mod = 998244353;
int f[maxn], col[maxn];
vector<pair<int,int> > edge[maxn];
bool flag;
int n, m,ans,sum=0; 
int find(int x){
    return f[x] == x ? x : f[x] = find(f[x]);
}
bool unionn(int x,int y)
{
    return find(x) != find(y);
}
void init()
{
        for (int i = 1; i <= n; ++i) f[i] = i;
}
void dfs(int u, int p){
    if (!flag) return;
    int v,w;
    for (int i = 0; i < edge[u].size(); ++i){
        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 u, v, w;

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

    ans = n;

    init();

    for (int i = 1; i <= m; ++i)
    {
       scanf("%d%d%d",&u,&v,&w);
        if (unionn(u,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);

    flag = 1;
    for (int i = 1; i <= n; ++i)
    {
        if (col[i] == -1)
        {
            col[i] = 0;
            dfs(i, i);
            sum++;
        }
    }
    if (!flag)
    {
        cout << 0 << endl; return 0;
    }
    ll ans = 1;
    for (int i = 0; i < sum-ans; ++i) ans = ans*2%mod;
    cout << ans << endl;
    return 0;
}