Codeforces Round #309 (Div. 1), problem: (C) Love Triangles

可以發現love的關係是等價關係，
然後這世界只有兩種值: 0, 1

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
using namespace std;

typedef long long int int64;
const int64 P = 1000000007;

typedef vector<int> VI;

int Fat(VI& fat, int a){return (fat[a] == a) ? a: fat[a] = Fat(fat, fat[a]);}
void Onion(VI& fat, int a, int b){fat[Fat(fat, a)] = Fat(fat, b);return;}

struct _rel{int a, b, c;};

_rel rel[100000];

int main(){
    int n, k; scanf("%d %d", &n, &k);
    for(int lx = 0;lx < k;lx++){
        scanf("%d %d %d", &rel[lx].a, &rel[lx].b, &rel[lx].c);
        rel[lx].a--, rel[lx].b--;
    }

    VI test(2*n);
    for(int lx = 0;lx < 2*n;lx++) test[lx] = lx;
    for(int lx = 0;lx < k;lx++){
        if(rel[lx].c)
            Onion(test, rel[lx].a, rel[lx].b),
            Onion(test, rel[lx].a+n, rel[lx].b+n);
        else
            Onion(test, rel[lx].a, rel[lx].b+n),
            Onion(test, rel[lx].b, rel[lx].a+n);
    }
    
    bool check = true;
    for(int lx = 0;lx < n and check;lx++)
        if(Fat(test, lx) == Fat(test, lx+n))
            check = false;
    if(!check){
        puts("0");
        return 0;
    }

    for(int lx = 0;lx < n;lx++)
        Onion(test, lx, lx+n);

    set<int> sign;
    int64 ans = (1+P)/2;
    for(int lx = 0;lx < n;lx++){
        if(sign.count(Fat(test, lx))) continue;
        ans = (ans*2)%P;
        sign.insert(Fat(test, lx));
    }

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

    return 0;
}