M27306: 植物观察

disjoint set, bfs, http://cs101.openjudge.cn/practice/27306/

思路：典型二分图判断

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 105;  
int parent[MAX_N];     
int relation[MAX_N];    
void init(int n) {
    for (int i = 0; i < n; ++i) {
        parent[i] = i;  
        relation[i] = 0; 
    }
}
int find(int x) {
    if (parent[x] != x) {
        int origin_parent = parent[x];
        parent[x] = find(parent[x]); 
        relation[x] ^= relation[origin_parent];
    }
    return parent[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    init(n);
    bool possible = true;  
    for (int i = 0; i < m; ++i) {
        int a, b, op;
        cin >> a >> b >> op;
        int root_a = find(a);
        int root_b = find(b);
        if (root_a == root_b) {
            if ((relation[a] ^ relation[b]) != op) {
                possible = false;
            }
        } else {
            parent[root_b] = root_a;
            relation[root_b] = relation[a] ^ relation[b] ^ op;
        }
    }
    cout << (possible ? "YES" : "NO") << endl;
    return 0;
}