【每日一题】边的染色

题目

题目描述：
小团有一张n个点，m条边的无向图G，有些边上已经被标记了0或1，表示它的边权。
现在你需要给剩下的边标记边权为0或1，求有几种标记的方式满足：
对于G中任意一个环，里面所有边的边权的异或值为0。
环的定义如下：
对于任意k（k≥2）个点{a1,a2,...,ak}，若对于所有的i<k满足ai与ai+1之间有边，且a1=ak成立，则这k个点构成一个环。

输入描述：
第一行两个整数n, m。
接下来m行，每行3个整数u, v, w，表示有一条边(u,v)，若w=-1则这条边上没有标记，否则w=0或1表示这条边上标记了w。
数据保证没有重边和自环。
1≤n≤100,000

0≤m≤min(n*(n-1)/2, 100000)

输出描述：

输出方案数对998,244,353取模的值。

解析

首先我们要了解思路再考虑做法：（要命，今天我看了五六个小时，虽然很长时间在研究代码怎么写）

异或的概念想必都知道，相同为0，不同为1。
但是边是真的不好下手，所以我们这一步就非常重要了：将我们要计算的边权化为点权。（就是每个点分别有自己的权值）
但是点权又怎么下手呢？又开始疑惑了。我们现在知道每个点假设涂色两种（0/1），我们能知道一共有2ⁿ种涂色方法。
但是这些全是吗？是的！（在不限定边权的情况下）：因为所有边权化为所有点权的时候（一边对两点），每个点都操作了两次，抵消了！
我们举个栗子，有四个点（a,b,c,d）边权分别为：a^b,b^c,c^d,d^a。如果全部异或起来就有a^b^b^c^c^d^d^a：两两对应，当然为0。
我们知道了点的方法数，再来推出边的方法数：由于点权得到边权只有两种方案，所以点权就是边权的两倍：2^n-1。（不在同一个环里面的话乘起来就好了，答案不变）
但是我们现在有边权！边权给了我们一些限制。但是这很好理解！加入你已知了一些边权，以边权可以抵达的某一点出发，已知这个点，其他点都能算出来。
意思就是说，我们只要知道有几组边权连通图就行了。加入有k个，我们只要去掉2^k-1组情况就行了。所以答案就是2^n-k。

这个大佬超详细，借鉴这个代码

然后更重要的是！代码怎么写！

这里用到了一个我不会的新概念就是前向星（点开看专栏）。
其实知道前向星怎么用以后就不难了。我们首先该存的存进前向星结构体数组里面。
然后要进行一个判断：题目给我们的可能本来就不成立，那我们只要判断，我们推算出来的边权和题目边权不一样就行了。（就是题目的边权条件互斥）
如果互斥输出个0，然后结束就好了。如果不是呢我们就进入下一步。
我们再只要遍历算出总节点数量（得到中点权推算出总边权），和有边权节点数量（删除这些组的可能性）。
最后来个快速幂输出就好了！！！！！
剩下来看我详细的代码吧！（累了，困了）

AC代码

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
//代码预处理区

const int MOD = 998244353;
const int MAX = 1e5 + 7;
int n, m;//总点数，总边数
int head[MAX], total = 1;//前向星：查找数组，计数
int color[MAX], visited[MAX];//每节点颜色数组，观测数组
struct EDGE {
    int me, next, val;
    EDGE() {};
    void init(int from, int to, int val) {
        this->me = to;
        this->next = head[from];
        this->val = val;
        head[from] = total++;
    }
} edge[MAX << 1];
//全局变量区

template<class T>inline void read(T& res);//整型快读函数
int check(int node, int col);//检查题目合法性函数
void get_all(int node, int& sum);//计算连通块总节点数
void get_del(int node, int& sum);//计算连通块被删除节点数
ll qpow(ll n, ll m);//快速幂
//函数预定义区

int main() {
    read(n); read(m);
    for (int i = 1; i <= m; i++) {
        int u, v, w; read(u); read(v); read(w);
        edge[total].init(u, v, w);
        edge[total].init(v, u, w);
    }
    //前向星初始化
    memset(color, -1, sizeof(color));
    for (int i = 1; i <= n; i++)
        if (color[i] == -1)
            if (!check(i, 1)) {
                printf("0\n");
                return 0;
            }
    //题目合法性判断，不合法直接输出0并结束
    int cnt = 0;//计算指数
    memset(visited, 0, sizeof(visited));
    for (int i = 1; i <= n; i++) {
        int sum = 0;//连通块总节点数
        if (!visited[i]) {
            get_all(i, sum);
            cnt += sum - 1;
        }
    }
        //加上没有边权的情况下的指数大小
    memset(visited, 0, sizeof(visited));
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        if (!visited[i]) {
            get_del(i, sum);
            cnt -= sum - 1;
        }
    }
        //减去边权所占用的指数大小
    cout << qpow(2, cnt) << endl;
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
int check(int node, int col) {
    color[node] = col;
    for (int i = head[node]; i; i = edge[i].next) {
        int to = edge[i].me;//当前节点连接的下一个节点
        int weight = edge[i].val;//当前节点与下一节点之间的边权
        if (weight == -1) continue;
        //没有边权位置一定存在
        if (color[to] != -1)
            if (color[node] ^ color[to] != weight)
                return 0;
            else;
        //有颜色则判断是否相等
        else
            if (!check(to, col ^ weight)) 
                return 0;
        //无颜色则继续判断下一个节点
    }
    return 1;
} 
void get_all(int node, int& sum) {
    sum++;
    visited[node] = 1;
    for (int i = head[node]; i; i = edge[i].next)
        if (!visited[edge[i].me])
            get_all(edge[i].me, sum);
                //查找联通的点，每次查找一个环
}
void get_del(int node, int& sum) {
    sum++;
    visited[node] = 1;
    for (int i = head[node]; i; i = edge[i].next)
        if (edge[i].val != -1)
            if (!visited[edge[i].me])
                get_del(edge[i].me, sum);
                        //查找边权点

}
ll qpow(ll n, ll m) {
    ll mul = 1;
    while (m) {
        if (m & 1) mul = (mul * n) % MOD;
        m >>= 1;
        n = (n * n) % MOD;
    }
    return mul;
}
//函数区