题解 | 人人都是好朋友

由于节点数量太多，所以考虑使用哈希表优化的并查集，另外合并不使用递归防止深度过大发生段错误；

由于朋友之间具有传递性，所以可以把所有的朋友看作是一个集合，从这里可以想到使用并查集

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
#define pb push_back
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define vi vector<int>
#define vii vector<vector<int>>
#define fi first 
#define se second
#define eb emplace_back
#define in insert
#define pf push_front
const int inf = 2e18 + 9 ;
const int mod1 = 1e9 + 7 ; 
const int mod2 = 998244353 ; 
typedef pair<int, int> pll;
typedef long double db;

inline int gcd(int a , int b) {return b ? gcd(b , a % b) : a;};
template<class T>inline void read(T &res){char c;T flag=1;while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;}
inline int qsm(int a , int b){int res = 1 ; while(b){if(b & 1){res *= a ; }b >>= 1 ; a *= a ; }return res ; }
struct dsu
{
     unordered_map<int, int> pa;
    unordered_map<int, int> rank;
    int find(int x)
    {
        if (!pa.count(x)) 
        {
            pa[x] = x;
            rank[x] = 1;
        }
        while(pa[x] != x)
        {
            pa[x] = pa[pa[x]]; 
            x = pa[x];
        }
        return pa[x] ; 
    }
    void unite(int x , int y)
    {
        x = find(x) ; 
        y = find(y) ; 
        if(x == y)
        {
            return ; 
        }
        if(rank[x] > rank[y])
        {
            swap(x , y);
        }
        pa[x] = y ; 
        if(rank[x] == rank[y])
        {
            rank[y]++ ; 
        }
    }
};
void work() 
{
    int n ; cin >> n ; 
    dsu hao;
    vector<pll>a ; 
    for(int i = 1 ; i <= n ; i++)
    {
        int x , y , z ; cin >> x >> y >> z ;
        if(z != 1)
        {
            a.pb({x , y});
        }
        else 
        {
            hao.unite(x , y);
        }
    }
    for(size_t i = 0 ; i < a.size() ; i++)
    {
        auto [a1 , a2] = a[i];
        if(hao.find(a1) == hao.find(a2))
        {
            cout << "NO" << endl ; 
            return ; 
        }
    }
    cout << "YES" << endl ; 
}
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t ; 
    while (t--) 
    {
        work();
    }
    return 0;
}