【每日一题】边的染色

戳我传送

思路：

1.链式向前星存图后，dfs跑一遍判读是否自身矛盾。
2.dfs再跑一遍，对每个联通块的元素个数sum-1求和k。
3.dfs再跑一遍，对每个涂了颜色的边组成的连通块的元素个数sum-1求和，再用k减去总和，ans=2^k。

原理

1.边的值可以看作两个端点的异或值。
2.对每个涂了颜色的边组成的连通块，假设一个点为1，其余的点的值也随之确定了。比如1-3边的值为1，3-2边的值为0，如果给1取1，那么可以得到3=0，2=0。（这个联通快如果不是环，就不会自身矛盾，如果是环才有可能自身矛盾）如果又涂回到了起点（即这个连通块是圆），如果颜色和原来的一致就不矛盾，如果此时应该涂的颜色和第一次假设的颜色矛盾，那么存在自身矛盾，直接输出0。
3.思路的2和3都是从一个点遍历完整个连通块计算有多少个元素就是连通块的大小了。（一个联通快内可以有许多个环，一开始以为就一个）
3.一条边可以取0、1，两个点可以取0、0，0、1，1、0，1、1。两条边有四种可能，三个端点有8种可能。所以自由边的方案数是自由端点的方案数的1/2倍，假设某连通块有k个点，那么边的方案数等于2^(k-1)。

知道原理后，我们发现思路1的dfs跑图时，只要存那些染了色的边，没染色的边不需要存。思路2、3的dfs只是想要连通块的大小，这个并查集预处理一下就好了。复杂度 （n log n）

Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
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 fa[100005],size[100005],col[100005],f[100005],size2[100005];
int head[100005],Next[100005<<1],to[100005<<1],w[100005<<1],tot;
void add(int x,int y,int c) {
    to[++tot]=y;
    Next[tot]=head[x];
    w[tot]=c;
    head[x]=tot;
}
int find1(int x) {
    return fa[x]==0?x:(fa[x]=find1(fa[x]));
}
int find2(int x) {
    return f[x]==0?x:(f[x]=find2(f[x]));
}
bool dfs(int x,int c) {
    col[x]=c;
    for(int i=head[x];i;i=Next[i]) {
        int y=to[i];
        if(col[y]!=-1&&col[x]^w[i]!=col[y]) return 0;
        if(col[y]==-1&&!dfs(y,col[x]^w[i])) return 0;
    }
    return 1;
}
ll qpow(ll a,ll b) {
    ll ans=1;
    while(b) {
        if(b&1) ans=ans*a%998244353;
        a=a*a%998244353;
        b>>=1;
    }
    return ans;
}
int main() {
    int n,m,sum=0;
    read(n),read(m);
    fill(size+1,size+1+n,1);
    fill(size2+1,size2+1+n,1);
    while(m--) {
        int x,y,z,i,j;
        read(x),read(y),read(z);
        i=find1(x),j=find1(y);
        if(i!=j) {
            fa[i]=j;
            size[j]+=size[i];
        }
        if(z!=-1) {
            add(x,y,z);
            add(y,x,z);
            i=find2(x),j=find2(y);
            if(i!=j) {
                f[i]=j;
                size2[j]+=size2[i];
            }
        }
    }
    fill(col+1,col+1+n,-1);
    for(int i=1;i<=n;++i) {
        if(col[i]==-1&&!dfs(i,1)) {
            puts("0");
            return 0;
        }
        if(!fa[i]) sum+=size[i]-1;
        if(!f[i])    sum-=size2[i]-1;
    }
    printf("%lld\n",qpow(2,sum));
}