题解 | 人人都是好朋友

#include <bits/stdc++.h>
using namespace std;
const int N =5e6+10;
int fa[N];
int n;
int cnt;
int ai[N],bi[N],ci[N];

void init()
{
    for(int i=1;i<=2*cnt;i++)
    {
        fa[i]=i;
    }
}


int find(int i)
{
    return i==fa[i]?i:fa[i]=find(fa[i]);
}
void merge(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    if(fx==fy)
    {
        return ;
    }
    fa[fx] = fy;

}

void solve()
{
    cnt = 0;
    cin>>n;
    bool flag = false;
    vector<int>vec;
    for(int i=1;i<=n;i++)
    {
        cin>>ai[i]>>bi[i]>>ci[i];
        vec.push_back(ai[i]);
        vec.push_back(bi[i]);
    }

    sort(vec.begin(),vec.end());
    unordered_map<int,int>mp;
    int sz = vec.size();
    mp[vec[0]]=1;
    cnt = 1;
    for(int i=1;i<sz;i++)
    {
        if(vec[i]!=vec[i-1])
        {
            mp[vec[i]]=++cnt;
        }
    }

    for(int i=1;i<=n;i++)
    {
        ai[i] = mp[ai[i]];
        bi[i] = mp[bi[i]];
    }

    init();

    for(int i=1;i<=n;i++)
    {
        int a = ai[i];
        int b = bi[i];
        int c = ci[i];
        if(c==1)
        {
            if(find(a)==find(b+cnt)||find(b)==find(a+cnt))flag = true;
            merge(a+cnt,b+cnt);
            merge(a,b);
        }
        else 
        {
            if(find(a)==find(b)||find(b+cnt)==find(a+cnt))flag = true;
            merge(a,b+cnt);
            merge(a+cnt,b);
        }
    }

    if(flag)cout<<"NO\n";
    else cout<<"YES\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }


    return 0;
}

经典的种类并查集题目