边的染色

          题外话: 这题开始并没有什么思路,第二天参考并学习了雨神的思路和写法。感谢雨神大大和清楚姐^-^

          题意: 给出n个点和m条边的无向图,有一些边被‘0’或者‘1’染色了. 问你:给没有染色的边染色,使得一个环的异或值为0.求这样满足条件的环有多少种染色方案。

          首先，异或^ 。如果二进制同一位置上数相同,返回0,否则返回1. 如果2个相同的数异或一下，结果是0；不相同的数异或一下，结果是1.

          如果说从边不好下手的话,我们可以先从点开始分析，首先如果n个点进行0/1染色的话，有2^n次种方案。

          这2^n次种方案都是异或和为0? 答案是YES

          因为把2个点权异或成边权,每个点会被异或2次，2次相当于抵消了，所以结果就是0。看下图：

          那么把点的情况转化成边的情况的话,方案数会减少多少？

举一个例子：

          总的方案数其实就是连通块中有多少个节点，然后对应的方案数就是2^(k-1),但是现在题目有一个条件，就是说，他可能会给出一些边权，我们上面讨论的是无任何边权的情况。 有边权的话，在边权连出来的连通块中，只有一个点能选择0或者1，只要那个点被确定了，剩下的点都能唯一确定，因为他有边权的限制。我们把这个连通块的大小为k的话，答案要/2^(k-1)

          所以我们只要先求出所有的连通块的大小之和，然后减掉有边权的连通块的大小。
最后的结果就是2的个数，乘起来即可

          最后如果出现矛盾的情况，我们直接返回0.

矛盾样例如下:
4 4
1 2 1
2 3 1
3 4 1
4 1 0

结果 0

AC代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

const int N=100000+100;

const int MOD=998244353;

int head[N],tot;//链式前向星的变量

int n,m;//n个顶点,m条边
int x,y,val;//读入m条边的信息

int color[N];//存每个点染的颜色

int vis[N];//这个点是否被标记

int sum;

struct Edge
{
    int e;
    int to;
    int val;
}edge[N<<1];

void add_edge(int u,int v,int val)
{//加边操作
    tot++;
    edge[tot].e=v;
    edge[tot].to=head[u];
    edge[tot].val=val;
    head[u]=tot;
}

int dfs(int u,int col)//u表示当前节点,col表示涂的颜色
{
    color[u]=col;
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        int v=edge[i].e;//和当前u节点相连的下一个节点 v
        int w=edge[i].val;//和当前u节点相连的下一个节点v的边权
        if(w==-1)continue;//我们只看边权有的
        if(color[v]!=-1)
        {//如果节点v已经被染过色了,那么我们需要和u节点异或一下,看看结果和他两直接的边权吻合吗
            if(color[u]^color[v]!=w)
            {//如果不等于,就发发生矛盾了
                return 0;
            }
        }
        if(color[v]==-1)
        {//如果节点v没有被颜色,那么就递归染色下去

            int t=dfs(v,col^w);//下一个点的颜色是边权异或前一个颜色,这样能保证2个节点异或一下等于他的边权
            if(t==0)return 0;
        }
    }
    return 1;
}

void dfs1(int u)
{
    sum++;
    vis[u]=1;
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        int v=edge[i].e;
        if(!vis[v])dfs1(v);
    }
}

void dfs2(int u)
{
    sum++;
    vis[u]=1;
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        int v=edge[i].e;
        int w=edge[i].val;
        if(w==-1)continue;
        if(!vis[v])dfs2(v);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    //n个顶点,m条边
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&x,&y,&val);
        //val=-1表示没有标记,0或者1表示标记了

        //无向图正反存2次
        add_edge(x,y,val);
        add_edge(y,x,val);
    }

    memset(color,-1,sizeof(color));//-1表示这个点没有被标记颜色

    //首先我们要看已经被标记的边是不是存在前后矛盾的情况,如果存在直接输出0

    for(int i=1;i<=n;i++)
    {
        if(color[i]==-1)//如果当前的颜色没有被标记过
        {
            int f=dfs(i,1);//把这个点先涂上颜色为1
            if(f==0)
            {//出现矛盾
                printf("0\n");
                return 0;
            }
        }
    }


    //求连通块点的个数

    memset(vis,0,sizeof(vis));

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        sum=0;
        if(!vis[i])
        {
            dfs1(i);
            ans+=(sum-1);
        }
    }

    memset(vis,0,sizeof(vis));

    for(int i=1;i<=n;i++)
    {
        sum=0;
        if(!vis[i])
        {
            dfs2(i);
            ans-=(sum-1);
        }
    }

    ll res=1;
    for(int i=0;i<ans;i++)
    {
        res=(res*2ll)%MOD;
    }

    printf("%lld\n",res);

    return 0;
}