CF553C Love Triangles

题目链接

题意：给定n个点，给出一些边权为0/1的边，构造完全图，满足对于任何一个三元环，三条边权和为奇。求符合条件的完全图数量，对\(1e9+7\)取模。

分析：其实原题给定的边权是love/hate，love即1，hate即0。

所以对于三元环而言，只存在“爱爱爱”或“爱恨恨”。

如果我们按此讨论点与点之间的关系，我们会想到什么？

那么这道题就和[BOI2003]团伙的描述有些类似了。

我们显然可以用到并查集。

团伙那题，我们确定两点关系可以建立补集，也可以使用带权并查集。

这题，我们发现，一个集合是否有补集在统计答案时并无差别（都相当于一个点），所以我们使用带权并查集。

带权并查集的方法就十分显然了，对于love的边，连一条权值为0的边，对于hate的边，连一条权值为1的边（注意与题目所给的相反）。每次连边是顺便检查两点关系。

最后我们得到\(k\)个集合，把\(k\)个集合放入两个桶中，有\(2^k\)种方法，再去重，最后的答案就是\(2^{k-1}\)

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int fa[100100], val[100100];//fa是所在集合，val是与祖先关系

inline int read()// Fast input

{

    int x=0,f=1; char ch=getchar();

    for (; ch<'0' || ch>'9'; ch=getchar()) if (ch=='-') f=-1;

    for (; ch>='0' && ch<='9'; ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';

    return x*f;

}

int find(int x)//带权并查集

{

    if (fa[x]==x) return x;

    int t=find(fa[x]);

    val[x]^=val[fa[x]];

    return fa[x]=t;

}

int main()

{

    int n=read(), k=read();

    for (int i=1; i<=n; i++) fa[i]=i;

    for (int i=1; i<=k; i++)

    {

        int u=read(), v=read(), w=read()^1;

        int fu=find(u), fv=find(v);

        if (fu!=fv)

        {

            fa[fv]=fu;

            val[fv]=val[u]^val[v]^w;

        }

        else

        {

            if (w && !(val[u]^val[v])) {puts("0"); return 0;}

            if (!w && val[u]^val[v]) {puts("0"); return 0;}

        }

    }

    int res=0, ans=1;

    for (int i=1; i<=n; i++) if (find(i)==i) res++;

    for (int i=1; i<=res-1; i++) ans=(ans*2)%mod;//（其实可以写quick_power的qwq

    printf("%d\n",ans);

    return 0;

}