程序自动分析-并查集+离散化

· · 题解

题意

给定n对条件的是否等价的关系，要求最后这些条件是否能够被同时满足。

思路

对于等价的关系维护一个集合，对于不等价的关系，判断是否位于同一个集合，若是则不能满足。但是考虑到条件的数据规模很大，因此可以使用map对每个条件进行离散化操作，使得每个条件对应的下标落在小规模的范围内。

算法

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

const int N=2e5+10; // 定义为n的两倍

int p[N];

int find(int x) {
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

struct cdt{
    int a,b,c;
};

bool cmp(cdt a,cdt b) {
    return a.c>b.c;
}

void solve() {
    int n;
    cin>>n; // 注意n在这里只是表示关系数，而非并查集的元素个数
    // 因此并查集中的元素个数最多2*n个
    for(int i=1;i<=2*n;i++) p[i]=i;
    vector<cdt> a;
    map<int,int> index;// 使用map进行离散化
    for(int i=0,cnt=1;i<n;i++) {
        int x,y,z;
        cin>>x>>y>>z;
        a.push_back({x,y,z});
        if(!index[x]) index[x]=cnt++; 
        if(!index[y]) index[y]=cnt++;
    }
    sort(a.begin(),a.end(),cmp);
    for(int i=0;i<n;i++) {
        int x=index[a[i].a],y=index[a[i].b],z=a[i].c;
        if(z) {
            p[find(x)]=find(y);
        }
        else if(find(x)==find(y)) {
            puts("NO");
            return;
        }
    }
    puts("YES");
    return;
}

int main() {
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

总结