前言:

思维不够,看到这种陌生的题目无从下手.

思路:

这题应该做过一次的人会觉得它其实并不难.
主要思想:把边权->点权.
这样做的好处是,无论你怎么分配点权,在环内的异或值一定为(前提是环内的一定合法.)
做题步骤也是围绕这些性质来的.
1.首先判断给定的点是否有矛盾,就是你给一个点赋值,它假如是环的话,有矛盾,那么它的异或值为.然后你这个点的异或值会和你之前给定它的异或值不同.
2.找有多少联通块,不同的联通块是独立事件,用乘法原理.然后点权的设置,其实本身存在重复,就是你把所有点取反和不取反,这两种情况的边权是一样的.然后本身没有限制,假设联通块大小是,那么就是.去除重复就是.
3.考虑限制,一旦给一段连续的限制,你给头部元素赋值,它这一段都是确定的,换句话来说,它这一段的贡献只有.所以我们应该把之前多算的贡献消掉,假如这段联通块大小是,那么我们必须把.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mod=998244353;
struct graph{
    int to,val;
};
vector<graph>g[N];
int color[N];//给n个点染色,判断是否成立.
bool vis[N];//标记这个点是不是遍历过. 
bool dfs0(int u,int col)
{
    color[u]=col;
    for(auto v:g[u])
    {
        if(v.val==-1)    continue;
        if(color[v.to]!=-1&&col^v.val!=color[v.to])    return false;
        if(color[v.to]==-1&&!dfs0(v.to,col^v.val))    return false;
    }return true;
}

int dfs1(int u,bool op)
{
    int res=1;vis[u]=true;
    for(auto v:g[u])
    {
        if(op)    
            if(v.val==-1)    continue;
        if(!vis[v.to])    res+=dfs1(v.to,op);
    }return res;
}


int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }memset(color,-1,sizeof color);
    for(int i=1;i<=n;i++)
    {
        if(color[i]==-1)
        {
            if(!dfs0(i,1))
            {
                puts("0");return 0;
            }
        }
    }int k=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            k+=(dfs1(i,false)-1);
        }
    }memset(vis,false,sizeof vis);
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            k-=(dfs1(i,true)-1);
        }
    } ans=1;
    for(int i=1;i<=k;i++)
    {
        ans*=2,ans%=mod;
    }printf("%d\n",ans);
    return 0;
}