【Acwing】并查集 237. 程序自动分析

ゞ浴缸里的玫瑰 2024-04-01 18:20 93阅读 0赞

[237. 程序自动分析 - AcWing题库][237. _ - AcWing]

题意：

![22dc95f73e2e4940a03543930038d3b0.png][]

思路：

经典并查集维护关系传递性的题目，将相等的元素分为一类，然后询问的时候看这两个元素在不在同一连通块就好了

小trick：由于数据较大，因此需要离散化一下

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e5+10;
    #define int long long
    unordered_map<int,int> mp;
    struct ty{
        int a,b,w;
    }q[mxn];
    int n,x,y,w,tot=0;
    int f[mxn];
    int s(int x){
        if(mp[x]) return mp[x];
        return mp[x]=++tot;
    }
    void init(){
        tot=0;
        mp.clear();
    }
    int find(int x){
        return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1!=f2) f[f1]=f2;
    }
    void solve(){
        init();
        cin>>n;
        for(int i=1;i<=2e5;i++) f[i]=i;
        for(int i=1;i<=n;i++){
            cin>>x>>y>>w;
            x=s(x),y=s(y);
            q[i].a=x,q[i].b=y,q[i].w=w;
            if(w==1) join(x,y);
        }
        int ok=1;
        for(int i=1;i<=n;i++){
            if(!q[i].w){
                if(find(q[i].a)==find(q[i].b)){
                    ok=0;
                    break;
                }
            }
        }
        if(ok) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int T=1;
        cin>>T;
        while(T--)solve();
        return 0;
    }

[237. _ - AcWing]: https://www.acwing.com/problem/content/239/
[22dc95f73e2e4940a03543930038d3b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d8e90c983bb544419c01dd3fc56f3fc6.png