【每日一题】边的染色（dfs+思维 / 联通块+xor）

Solution
题意：给定一个无向图，有一些边已经染色，求让你染色剩下的边使得每个环的异或和都为0的方案数。

好难想!好难想!好难想!重要的事情要说三遍!

1.思维点：题解很巧妙，把对边染色转移到对点染色，取边为两个端点的xor，这样的话每个环的异或和肯定为0，因为每个点都xor了两次~

2.答案的贡献：
考虑一个联通块里面没有边被染色，那么每个点都有染成 0/1 的选择，设cnt为联通块中的点数目，那么可以考虑成 2^cnt， 但是想一下，因为是算边的染色方案而不是点的染色方案，如果对所有点取反，边权不变，所以每个联通块对答案的贡献为： 2^(cnt-1) 。

再考虑已经有x条边被染色的联通块，那么如果这些染色的边已经有一个点确定一个值，那么染色的边剩下的点的值就都确定了，所以每个连通块对答案的贡献要除以： 2^x (x条边有x+1个点)

3.判断合法性：类似于判断二分图染色一样，遍历已经确定的边和随便染上1/0，根据边权由点权异或得到判断是否冲突。

参考题解，用三个dfs来解决问题：
dfs1: 慢慢染色，看是否合法。
dfs2: 统计所有联通块的点数
dfs3: 统计有染色边的联通块中的点数

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
const int mo=998244353; const int mod=1000000007;

const int manx=1e5+5;

vector<pair<ll,ll> >g[manx];
ll col[manx],vis[manx];
ll cnt=0;

ll dfs1(ll u,ll co){
    col[u]=co;
    for(auto x: g[u]){
        ll v=x.fi,w=x.se;
        if(w==-1) continue;
        if(col[v]!=-1 && co^col[v]!=w) return 0;
        if(col[v]==-1 && !dfs1(v,co^w)) return 0;
    }
    return 1;
}

void dfs2(ll u){
    cnt++; vis[u]=1;
    for(auto x:g[u]){
        ll v=x.fi,w=x.se;
        if(vis[v]) continue;
        dfs2(v);
    }
}

void dfs3(ll u){
    cnt++; vis[u]=1;
    for(auto x:g[u]){
        ll v=x.fi,w=x.se;
        if(vis[v]||w==-1) continue;
        dfs3(v);
    }
}
int main(){
    ll n=read(),m=read();
    for(int i=1;i<=m;i++){
        ll u=read(),v=read(),w=read();
        g[u].pb(mp(v,w));  g[v].pb(mp(u,w));
    }
    memset(col,-1,sizeof(col));
    for(int i=1;i<=n;i++){
        if(col[i]==-1){
            if(!dfs1(i,1)){
                cout<<0<<endl;
                return 0;
            }
        }
    }
    ll k=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt=0;
            dfs2(i);
            k+= cnt-1;
        }
    }
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt=0;
            dfs3(i);
            k-= cnt-1;
        }
    }
    ll ans=1;
    for(int i=1;i<=k;i++){
        ans=ans*2;
        ans%=mo;
    }
    printf("%lld\n",ans);
    return 0;
}