4.23 边的染色

这题没看题解前是不会的 在看完雨姐的题解后 知道了这题的几个关键
1、我们直接来分析边的染色是比较复杂的 那么我们就把边的权值当做边的两点的异或值
那么题目要求的条件 环的异或和为0就已经达到了（相当于把每个点异或了两次）
2、如果题目不给边值 而是全部由我们来标的话
点有2^n次标法 但装换成边值 有两种点的标法是一样的 （把一种标法的1全部换成0 0换1）
于是总方案有2^n-1次（n个点的联通图）
3、但是题目给了我们一些边的值 那么又要怎么处理？
求出每个由已有边权的边组成的连通图的点数 这种连通图里能自由标的点的值只有一个 其他点的值就由边确定了 那么答案就要/2^k-1（此连通图有k个点）
PS：要注意一开始数据给的边的值就导致方案数为0的情况
代码里大部分都有注释

#include<bits/stdc++.h>
using namespace std;
const int p = 998244353;
const int N = 100010;
int n,m;
int head[N];
int col[N];
bool vis[N];
struct ty
{
    int t, next, col;
}edge[N<<1];
int sum = 0, cnt= 0;
int tot = 0;
void addedge(int x,int y, int z)
{
    tot++;
    edge[tot].t = y;
    edge[tot].col = z;
    edge[tot].next = head[x];
    head[x] = tot;
}
bool dfs0(int x, int c)///x表示当前节点,c表示涂的颜色(即 0 1 边权)
{
    col[x] = c;///染色
    for (int i = head[x]; i > 0; i= edge[i].next)
    {
        if (edge[i].col == -1) continue;    ///我们只看边权有的
        int y = edge[i].t;///和当前x节点相连的下一个节点 y
        if((col[y] != -1) && (c^edge[i].col) != col[y]) return 0;  ///y的颜色有  两个计算一下 不等就发生矛盾
        if(col[y] == -1 && dfs0(y, c^edge[i].col)==0)  return 0;  ///y无  y的颜色由x与边权算出来
    }
    return 1;
}
void dfs1(int x)
{
    vis[x] = 1;
    sum++;
    for (int i = head[x]; i > 0; i= edge[i].next)
    {
        int y = edge[i].t;
        if(!vis[y]) dfs1(y);
    }
}
bool dfs2(int x)
{
    vis[x] = 1;
    cnt++;
    for (int i = head[x]; i > 0; i= edge[i].next)
    {
        if (edge[i].col == -1) continue;    ///只走有颜色的边
        int y = edge[i].t;
        if(!vis[y]) dfs2(y);
    }
    return 1;
}

int main()
{

    scanf("%d%d",&n,&m);
    for (int i = 1; i <= m; i++)
    {
       int u,v,w;
       scanf("%d%d%d", &u, &v, &w);
       addedge(u, v, w);
       addedge(v, u, w);
    }

    memset(col, -1, sizeof(col));///-1表示这个点没有被标记颜色
    ///看标记的边是否存在前后矛盾
    for (int i = 1; i <= n; i++)
    {
        if(col[i]==-1)///如果当前的颜色没有被标记过
        {
            if (dfs0(i, 1) == 0)///把这个点先涂上颜色为1 看是否有矛盾
            {
                cout << 0 << endl;
                return 0;
            }
        }
    }

    memset(vis, 0, sizeof(vis));
    int k = 0;
    for (int i = 1; i <= n; i++)///搜索一遍把连通块情况统计一下
    {
        sum = 0;  ///sum存本连通块的总点数   没有限制的话本连通块方案数是2^(sum-1)
        if(!vis[i])
        {
            dfs1(i);  ///找连通块个数
            k = k + sum-1;
        }
    }

    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)///只走已经有边权的边 看这样的边的连通块情况
    {
        cnt = 0; ///cnt存有边有权值的本连通块中点的个数  cnt不为0时会使得方案数除以2^(cnt-1)
        if(!vis[i])
        {
            dfs2(i);
            k = k - (cnt-1);
        }
    }

    long long ans = 1;
    for (int i = 1; i <= k ;i++)
    {
        ans = (ans*2) % p;
    }
    cout << ans << endl;


    return 0;
}