[CF 553C] Love Triangles

作法：

首先把圖轉換成「兩人相愛若且唯若兩點之間連邊」，觀察這張圖會有什麼特性。首先當$A,B$連邊且$B,C$連邊時，$A,C$也要連邊，因此可以知道每個連通塊一定都是完全圖。再來如果有大於兩個的連通塊，那麼在三個連通塊中各挑一個點就形成了兩兩沒有連邊的三角形，和題意矛盾，因此至多只有兩個連通塊。這樣就轉換成經典問題了：給一張圖，還有一些「兩點之間同色」和「兩點之間異色」的條件，問有幾種塗兩色的方法。這只要先用 disjoint set 判有沒有可能，若有可能則答案為$2$的(連通塊數量$-1$)次方，其中這裡的圖是「當給定條件$x,y$同色或異色」時則在$x,y$之間連一條邊所得到的圖。

code :

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
const int maxn=100000+10 ;
void err(){printf("0\n") ; exit(0) ;}
 
int fa[maxn],fad[maxn] ;
int getfa(int x)
{
    if(fa[x]==x) return x ;
    int f=fa[x] , t=getfa(f) ;
    fad[x]=(fad[x]+fad[f])%2 ;
    return fa[x]=t ;
}
 
bool join(int x,int y,int dis)
{
    int x2=getfa(x) , y2=getfa(y) ;
    dis=(dis+fad[x]+fad[y])%2 ;
    if(x2!=y2)
    {
        fa[x2]=y2 ; fad[x2]=dis ;
        return 1 ;
    }
    else return dis==0 ;
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) fa[i]=i ;
    while(m--)
    {
        int x,y,d ; scanf("%d%d%d",&x,&y,&d) ;
        if(!join(x,y,d^1)) err() ;
    }
    int ans=(MOD+1)/2 ;
    for(int i=1;i<=n;i++) if(fa[i]==i)
        ans=ans*2%1000000007 ;
    printf("%d\n",ans) ;
}