边的染色（思维）

题目：

n个点，m条边的无向图。有些边被标记为0或1，有些还未标记。问你将剩下的边用0或1标记，满足图中所有环边权异或和为0的方案数。mod998244353

做法：

这题不会，看题解才懂。。
边权的方案不好弄，考虑点权。这里的思想就是，假如我确定了某个环上所有点的点权，使点权异或和为0。那么边（u，v）的边权用val[u]^val[v]得到，是满足边权异或和为0的。也就是点权与边权可以建立映射关系。但是请注意不是一一映射的关系。比如，点权(1,1)和(0，0)同时映射边权0。所以点权的2种方案对应边权的1种方案。而这两种点权方案互反。
首先我们用已标记的边新建一个图。然后我们选一个未标记的点u给它标记上0。（可1可0，我们只处理0就行）。我们发现由于新图中边权都是确定的，所以一旦确定u的标记，和u联通的点的标记也都确定了。dfs更新一下。然后重复以上选点u，标记0的步骤。并且我们记录一下一共选了几个起点u标记了0，记为cnt。
这一步做了什么呢？
求出了新图的联通块数cnt。也判定了有无解。（若在标记过程中出现冲突，就是无解的情况，输出0）
接下来我们把目光放在未标记的边上。这些边是确定方案的关键！
现在我们可以将这些未标记的边视为使新图中2个不连通的块联通的边。我们设新图中方案数1，每2个新图中的联通块被这些边联通，总方案数*2。为什么会这样呢？因为使新图的联通块联通相当于两个联通块起点u的标记有更多的选择。想象一下，若这条边是0，是一种方案，是1也是一种方案。分别对应于两个联通块起点u的选取。
所以，搞了这么多。答案其实就是，是新图和原图联通块数量差。当然，前提是没冲突。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 998244353;
int fa[N], col[N];
vector<pair<int,int> > g[N];
bool flag;
int getfa(int x){
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
void dfs(int u, int p){//染色过程
    if (!flag) return;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i].first, w = g[u][i].second;
        if (col[v] == -1){
            col[v] = col[u]^w;
            dfs(v, u);
        }else if (col[u]^col[v] != w){
            flag = false; return;
        }
    }
}
int main(void){
    IOS;
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    int block = n;
    for (int i = 1; i <= m; ++i){
        int u, v, w; cin >> u >> v >> w;
        if (getfa(u) != getfa(v)){
            block--, fa[getfa(u)] = getfa(v);//并查集，得到原图联通块数量
        }
        if (w != -1){
            g[u].push_back(make_pair(v, w));
            g[v].push_back(make_pair(u, w));//建新图
        }
    }
    memset(col, -1, sizeof col);
    int cnt = 0;
    flag = true;//flag代表有无冲突
    for (int i = 1; i <= n; ++i){
        if (col[i] == -1){
            col[i] = 0, dfs(i, i), cnt++;//选点，标记0，同时记录新图联通块数量cnt
        }
    }
    if (!flag){//有冲突
        cout << 0 << endl; return 0;
    }
    ll ans = 1;
    for (int i = 0; i < cnt-block; ++i) ans = ans*2%mod;//答案是2^(联通块数量差)
    cout << ans << endl; 
    return 0;
}