#include<bits/stdc++.h>
using namespace std;
#define ll long long

struct DSU {
    vector<int> sz, f;
    DSU(int n) {
        sz.assign(n + 1, 1);
        f.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) f[i] = i;
    }

    int root(int u) {
        if (u == f[u]) return u;
        return root(f[u]);
    }

    void merge(int u, int v) {
        u = root(u), v = root(v);
        if (u == v) return;
        if (sz[u] > sz[v]) swap(u, v);
        sz[v] += sz[u];
        f[u] = v;
    }

    int size(int u) {
        return sz[root(u)];
    }

    bool same(int u, int v) {
        return root(u) == root(v);
    }
};

void solve() {
    int m;
    cin >> m;

    vector<array<int, 3>> opt;
    vector<int> b;
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        b.push_back(x);
        b.push_back(y);
        opt.push_back({x, y, z});
    }

    sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end());

    for (auto &[x, y, z] : opt) {
        x = lower_bound(b.begin(), b.end(), x) - b.begin();
        y = lower_bound(b.begin(), b.end(), y) - b.begin();
    }

    int n = b.size();
    DSU dsu(n);

    for (auto [x, y, z] : opt) {
        if (z == 1) dsu.merge(x, y);
    }

    for (auto [x, y, z] : opt) {
        if (z == 0) {
            if (dsu.same(x, y)) {
                cout << "NO\n"; return;
            }
        }
    }
    cout << "YES\n";
}
signed main() {
    int t = 1;
    cin >> t;
    while (t--) solve();
}
/*
g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt
*/

1 条评论

  • @ 2026-8-3 9:34:05
    #include<bits/stdc++.h>
    #define int long long 
    using namespace std;
    const int N=2e5+100;
    int n,m;int fa[N];
    struct aaa{
    	int a,b,op;
    }g[N];
    unordered_map<int,int> mp;
    int father(int x){
    	if(x==fa[x]) return fa[x];
    	else return fa[x]=father(fa[x]);
    }
    void un(int a,int b){
    	int A=father(a),B=father(b);
    	if(A==B) return ;
    	fa[B]=A;
    }
    int o(int x){
    	if(mp.count(x)==false) mp[x]=++m;
    	return mp[x];
    }
    void so(){
    	cin>>n;
    	mp.clear();
    	for(int i=1;i<N;i++) fa[i]=i;
    	m=0;
    	for(int i=1;i<=n;i++){
    		int x,y,op;cin>>x>>y>>op;
    		g[i]={o(x),o(y),op};
    		if(op==1){
    			un(o(x),o(y));
    		}
    	}
    	for(int i=1;i<=n;i++){
    		int idx=g[i].op;
    		if(idx==0){
    			if(father(g[i].a)==father(g[i].b)){
    				cout<<"NO"<<"\n";
    				return ;
    			} 
    		}
    	} 
    	cout<<"YES"<<"\n";
    	return;
    }
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	int _;cin>>_;
    	while(_--){
    		so();
    	}
    }
    
  • 1

信息

ID
484
时间
ms
内存
MiB
难度
6
标签
递交数
169
已通过
49
上传者