边的染色题解

一点也不夸张看来差不多三天 各个大佬题解都取看，最后找到一个看懂了。

https://blog.csdn.net/jaihk662/article/details/80955631
看的这个大佬的学会了。
题意：我也看了很久 ，而且自测很多ac代码自己推了样列才完全弄懂，首先就是如果是环 那么必须要满足条件，环里面的所有边权^=0；如果是链那么就不管，随便搞，
题解，那么首先我们可以这样想，每条边的权值只可以是0|1，如果是环，那么我们是不是可以这样想，任何一条边的权值，我把它用该条边的两个端点各自假设一个权值，然后边权=左端点^右端点，是不是这样一来，无论我在这个环里面取什么都可以满足^和为0；
举列子：三个点1-2-3-1，这样一个环，三条边,边权1-2：a1^a2，边权2-3：a2^a3,边权3-1:a3^a1,那么我们把三个边权异或是不是=0，所以我们首先边转换为点来思考，那么现在是不是有N个点，然后每个点可以选择0|1，那么是不是就有2^n种，但是我们的环上是不是有可能有边权和相等呢，答案是肯定的，为什么，如果所有的边权取反一下，是不是答案就和这个边权和一样啦，是不是有一边有边权我们就应该除2，然后最后我们是不是可以找到一个环，再取找到该环被标记的边，该环所有种类数/2^（已经标记的个数-1），因为已经标记的就不是2的标记点次方，而是1了，因为已知嘛，为什么要-1，是因为我们是以点来计数的。

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
const int maxx=1e5+100;
const int mod=998244353;
struct node
{
    int x,val;
};
vector<node>ans[maxx];
 cnt,sum,ok,vis[maxx],scc[maxx];
ll all[maxx],er[maxx]= {1};
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=a*ans%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void dfs(int u)
{
    sum++;//第二次dfs使用来找连通块的个数
    for(int i=0;i<ans[u].size();i++)
    {
        if(ans[u][i].val==-1)
            continue;
        int v=ans[u][i].x;
        int val=vis[u]^ans[u][i].val;
        if(vis[v]==-1)
        {
            vis[v]=val;
            dfs(v);
        }
        else if(vis[v]!=val)//每次判断是否构成的环能否满足题意
            ok=1;
    }
}
void dfs2(int u,int k)
{
    sum++;记录该父节点的所有儿子
    scc[u]=k;
    for(int i=0;i<ans[u].size();i++)
    {
        int v=ans[u][i].x;
        if(scc[v]==0)
            dfs2(v,k);
    }
}
int main()
{
    fio;
   /// cout<<(4>>1)<<endl;
    int x,y,val,n,m;
    cin>>n>>m;
    for(ll i=1; i<=m; i++)
    {
        cin>>x>>y>>val;
        ans[x].push_back(node{y,val});
        ans[y].push_back(node{x,val});
        ///cout<<ans[x][0].x<<" "<<ans[x][0].val<<endl;
    }

    for(int i=1; i<=n; i++)
        er[i]=er[i-1]*2%mod;//cout<<er[i]<<endl;;
        //memset(vis,-1,sizeof vis);
         mse(vis,-1);
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==-1)
        {
            vis[i]=0;///试试改为一
            dfs(i);
        }
    }
    if(ok)
        cout<<0<<endl;
    else
    {
    ll daan=1;
        for(int i=1;i<=n;i++)
        {
            if(scc[i]==0)
            {
                sum=0;
                dfs2(i,++cnt);//cnt代表如果此无向图非联通，有多个环，那么就是分成不同的连通块来计算，最后相乘
//该dfs2里面是找连通块个数，
                all[cnt]=er[sum-1];
            }
        }
        //memset(vis,-1,sizeof vis);
        mse(vis,-1);
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==-1)
            {
                sum=0;
                vis[i]=0;
                dfs(i);//本次就是找所有i的儿子，
                all[scc[i]]=all[scc[i]]*qpow(er[sum-1],mod-2)%mod;//逆元求法
        }
            }
                for(int i=1;i<=cnt;i++)
                    daan=daan*all[i]%mod;
                cout<<daan<<endl;
    }
    return 0;
}