Question

张纸条，上面写着三个整数。

  • 若表示和为朋友。
  • 否则表示其为敌人。

朋友的朋友也是朋友，问是否有矛盾的情况？

Solution

离散化 并查集
矛盾的情况为既是朋友又是敌人，很容易想到利用并查集去处理这里的关系。
"牛可乐的手下有 1e9 个"这句话是告诉我们直接开数组是要MLE的，结合数据范围以及题意，发现与数据的绝对大小无关，至于他们的相对顺序有关，故进行数据离散化预处理。

  1. 离散化
  2. 将关系为朋友的合并
  3. 查询关系为敌人的是否为朋友

坑点：数组要开>2e6，记得清空vector。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e6 + 5;

int n,f[N],a[N],b[N],c[N];
vector<int>V(N);

inline void init(int x) {for(int i=0;i<=x;i++) f[i]=i;}

inline int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}

inline void merge(int x,int y){
    int u=find(x),v=find(y);
    if(u!=v) f[v]=u;
}

inline void discreate(){
    V.clear();
    for(int i=1;i<=n;i++){
        V.push_back(a[i]);
        V.push_back(b[i]);
    }
    sort(V.begin(),V.end());
    V.erase(unique(V.begin(),V.end()), V.end());
}

inline int query(int x){
    return lower_bound(V.begin(), V.end(), x)-V.begin();
}

void solve(){
    cin>>n;
    bool flag=true;
    for(int i=1;i<=n;i++){cin>>a[i]>>b[i]>>c[i];}
    discreate();
    init(V.size());
    for(int i=1;i<=n;i++){
        if(c[i]==1) merge(query(a[i]),query(b[i]));
        else{
            if(find(query(a[i]))!=find(query(b[i]))) continue;
            flag=false;
            break;
        }
    }
    cout<<(flag?"YES":"NO")<<'\n';
}

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