【每日一题】边的染色

这个题目其实需要一点思维。
关键是要能够想到对于边染色，可以转到对于点去染色，而且我们规定，边颜色等于两个顶点的异或值。
仔细想想，如果这样的话我的点可以随便染色，都能够满足环的异或值为0，因为，每个点会连2条边，会异或2次，怎么样都是0.
还有一个要注意的点就是，对于n个点有2^n种染色方法，但是会有重复，需要除以二。

知道了这个的话，就好做了。我们只要去找到有多少个连通块，有多少个已经染色的点，这里要判断一下是否产生了矛盾，有矛盾的话直接输出0.否则的话根据公式计算

ANS=2^(K-1) K为未染色的点个数。

具体见代码，写了注释：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=100010;
int tot,sum,cnt;
int h[100010];
int col[100010];
bool vis[100010];
struct edge{
    int to,next,color;
}e[N*2];
void add(int u,int v,int w)
{
    ++tot;
    e[tot].to=v;
    e[tot].next=h[u];
    e[tot].color=w;
    h[u]=tot;
}
int n,m;
bool dfs0(int x,int c)  //判断是否有矛盾
{
    col[x]=c;
    for(int i=h[x];i>0;i=e[i].next)
    {
        if(e[i].color==-1) continue;   //只走有颜色的
        int y=e[i].to;
        if((col[y]!=-1)&&(c^e[i].color)!=col[y])  return 0; //出现了矛盾
        if(col[y]==-1&&dfs0(y,c^e[i].color)==0)  return 0;
    }
    return 1;
}

void dfs1(int x)
{
    vis[x]=1;
    sum++;
    for(int i=h[x];i>0;i=e[i].next)
    {
        int y=e[i].to;
        if(!vis[y]) dfs1(y);
    }


}
void dfs2(int x)
{
    vis[x]=1;
    cnt++;
    for(int i=h[x];i>0;i=e[i].next)
    {
        if(e[i].color==-1) continue;
        int y=e[i].to;
        if(!vis[y]) dfs2(y);
    }

}
int main()
{
    cin>>n>>m;
    for(int _=0;_<m;_++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    memset(col, -1, sizeof(col));
    for (int i = 1; i <= n; i++)//搜索一遍看是不是自己的边矛盾了——只走已经有边权的边
    {
        if(col[i]==-1)
        {
            if (dfs0(i, 1) == 0)   //给i点赋值为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) % mod;
    }
    cout << ans << endl;


    return 0;
    return 0;
}