并查集

对于每一组相等关系，必然具有传递性，可以将其划分为同一个集合，对于每一组不等关系a，b，必然有a所代表的集合中的元素与b所代表的集合中的元素各不相等
使用并查集，先将元素分类，在寻找是否有不合法的

#include <iostream>
#include <unordered_map>

using namespace std;

int t, n;
unordered_map<int, int>f;

int search(int a)
{
    if(f[a] == a) return a;
    return f[a] = search(f[a]);
}

void merge(int a, int b)
{
    //a的父节点换为b的父节点
    f[search(a)] = search(b);
}

struct r{
    int a, b, e;
}x[100005];

int main()
{
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        bool can = true;
        f = unordered_map<int, int>();
        for(int i = 0; i < n; i++)
        {
            int a, b, e;
            cin >> a >> b >> e;
            x[i].a = a;
            x[i].b = b;
            x[i].e = e;
        }
        for(int i = 0; i < n; i++) 
        {
            int a = x[i].a, b = x[i].b, e = x[i].e;
            if(e == 1)
            {
                if(f.find(a) == f.end() && f.find(b) != f.end()) f[a] = a;
                else if(f.find(a) != f.end() && f.find(b) == f.end()) f[b] = b;
                else if(f.find(a) == f.end() && f.find(b) == f.end()) f[a] = a, f[b] = b;
                merge(a, b);
            }

        }
        for(int i = 0; i < n; i++)
        {
            int a = x[i].a, b = x[i].b, e = x[i].e;
            if(e == 0)
            {
                if(f.find(a) != f.end() && f.find(b) != f.end())
                {
                    if(search(a) == search(b))
                    {
                        can = false;
                        break;
                    }
                }
                else if(f.find(a) == f.end() && f.find(b) != f.end()) f[a] = a;
                else if(f.find(b) == f.end() && f.find(a) != f.end()) f[b] = b;
                else f[a] = a, f[b] = b;
                if(a == b)
                {
                    can = false;
                    break;
                }
            }
        }
        if(can) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}