题意

对给定图进行 01 染色，每条边描述了两个点是同色或者异色，求染色方案数。

思路

因为只有两种颜色，所以连通块中只要有任何一个点的颜色确定了，就可以确定其他点的颜色，因此每个连通块如果可以进行二分图染色，则必然有两种不同的染色方法，$K$ 个连通块则有 $2^K$ 种染色方法。如果有一个连通块无法二分图染色，则总的染色方案为 $0$。我们依次找到每个连通块并进行模拟染色即可。

复杂度

时间

遍历图 $O(N+M)$。

空间

记录图 $O(N+M)$。

CODE

#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 1e5 + 1;
struct V {        // 点
  int c;          // 染色
  vector<pair<int, int>> e;  // 邻边
} v[kMaxN];
int n, m, x, y, t;
char ch;
void S(int x, int c) {      // 点x染色c
  if (v[x].c) {             // 已经染色
    if (v[x].c != c + 1) {  // 与之前的染色不同
      t = -n;               // 标记无解
    }
    return;
  }
  v[x].c = c + 1;          // 染色
  for (auto i : v[x].e) {  // 遍历邻边
    S(i.first, c ^ i.second);
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> ch >> x >> y;
    v[x].e.push_back({y, ch == 'D'}), v[y].e.push_back({x, ch == 'D'});
  }
  for (int i = 1; i <= n; i++) {  // 枚举点
    if (!v[i].c) {                // 找到新的连通块
      S(i, 0);                    // 染色
      t++;                        // 累加数量
    }
  }
  cout << (t > 0 ? "1" + string(t, '0') : "0");
  return 0;
}