P1955 程序自动分析 题解

P1955 程序自动分析

一道并查集的裸题，并查集存储传递性，后判断。主题思路十分简单，重点在于离散化与离线的处理。

离散化，为什么会想到离散化呢，观察数据范围 \(1<i,j<{10}^9\) ，数据范围过大，导致数组不可能开到 \(1e9\) 但是 \(1<n<1e5\) 考虑到每次输入只有两个数，若每个数都两两不同，则极限大小为 \(2e5\) 在可接受范围之内，用 \(map\) 来初始化，由于关心的是其两个数之间的逻辑关系，与其大小并无关系，所以省去按大小排序这一步。

离线处理，并查集维护相等关系，由于相等具有传递性 \(a_i=a_j,a_j=a_k则有a_i=a_k\) ,但是不等不具有传递性 \(a_i \ne a_j,a_j \ne a_k那么a_i不一定不等于a_k\) 但由于其要构成矛盾，则先判断相等与先判断不等无区别，所以离线操作，先维护相等并查集，再对于不等关系判断是否矛盾，输出即可。

#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 1e5+10,mod=1e9+7;
struct node{
    int x,y;
    int e;
}a[maxn<<1];
int fa[maxn<<1];
void in_it(int n){
    seq(i,1,2*n){
        fa[i]=i;
        a[i]={0,0,0};
    }
}
int find(int x){
    if(fa[x]==x){
        return x;
    }
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    int f1=find(x),f2=find(y);
    if(f1==f2) return;
    fa[f2]=f1;
}
int t,tot,n;
ll x,y;
map<ll,int>mp;
bool cmp(node x,node y){
    return x.e>y.e;
}
bool cmp1=0;
signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--){
        mp.clear();
        cmp1=0;
        tot=0;
        cin>>n;
        in_it(n);
        seq(i,1,n){
            cin>>x>>y>>a[i].e;
            if(!mp[x]) mp[x]=++tot;
            if(!mp[y]) mp[y]=++tot;
            a[i].x=mp[x];
            a[i].y=mp[y];
        }
        sort(a+1,a+1+n,cmp);
        int num=1;
        while(a[num].e){
            merge(a[num].x,a[num].y);
            num++;
        }
        seq(i,num,n){
            if(find(a[i].x)==find(a[i].y)){
                cmp1=1;
                break;
            }
        }
        if(cmp1){
            cout<<"NO"<<"\n";
        }
        else{
            cout<<"YES"<<"\n";
        }
    }
    return 0;
}