【每日一题】边的染色 题解

Solution

看了半天题解才看懂
我们先把边的异或转化成点的异或, 这里有个注意的坑
每一个点有两种取法, 总的是
但是对于边的取法, 因为对于他的两个端点, 都取反后边不改变, 所以对于边的取法是
这样我们就实现了连通图的任意环所有边权异或为0的总方案
但是题目的限定是有边权些已经给了值
对于一条已经被赋值的边
如果知道其中一个端点的值, 那么另一个端点也相应地被确定
因此我们可以从这个角度出发找寻是否有矛盾 解决不存在的子问题
接下来只需要先统计所有的连通块总点数贡献
然后除去那些被唯一确定的连通块贡献(假设连通块数量为 , 要除去

Code

/*
  autor: Kurisu
  2020年4月24日10:17:35
*/
#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;
const int N = 5e5 + 5;
const double eps = 1e-10;
const int mod = 998244353;

struct Edge{
  int v, nextz, col;
}edge[N << 1];
int head[N], col[N], vis[N], tot, n, m, res, sum;

void addedge(int u, int v, int w) {
  edge[tot].v = v;
  edge[tot].nextz = head[u];
  edge[tot].col = w;
  head[u] = tot++;
}
bool dfs0(int u, int cor) {
  col[u] = cor;
  for (int i = head[u]; ~i; i = edge[i].nextz) {
    if(edge[i].col == -1) continue;
    int v = edge[i].v;
    if((col[v] != -1) && (cor ^ edge[i].col) != col[v]) return false;
    if((col[v] == -1) && !dfs0(v, cor ^ edge[i].col)) return false;
  }
  return true;
}
void dfs1(int u) {
  vis[u] = 1;
  sum++;
  for (int i = head[u]; ~i; i = edge[i].nextz) {
    int v = edge[i].v;
    if(!vis[v]) dfs1(v);
  }
}
bool dfs2(int u) {
  vis[u] = 1;
  res++;
  for (int i = head[u]; ~i; i = edge[i].nextz) {
    if(edge[i].col == -1) continue;
    int v = edge[i].v;
    if(!vis[v]) dfs2(v);
  }
  return true;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  memset(head, -1, sizeof(head));
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    addedge(u, v, w);
    addedge(v, u, w);
  }
  memset(col, -1, sizeof(col));
  for (int i = 1; i <= n; i++) {
    if(col[i] == -1) {
      if(!dfs0(i, 1)) {
        cout << "0\n";
        return 0;
      }
    }
  }
  long long cnt = 0;
  for (int i = 1; i <= n; i++) {
    sum = 0;
    if(!vis[i]) {
      dfs1(i);
      cnt += sum - 1;
    }
  }
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i <= n; i++) {
    res = 0;
    if(!vis[i]) {
      dfs2(i);
      cnt = cnt - (res - 1);
    }
  }
  long long ans = 1;
  for (int i = 1; i <= cnt; i++) {
    ans = (ans * 2) % mod;
  }
  cout << ans << "\n";
  return 0;
}