審題：

本題需要我們判斷是否可以同時滿足題目給定的若干等式或不等式，判斷出后根據結果輸出YES或NO

思路：
方法一：離散化+并查集

使用并查集：其實題目中只存在兩者相等或不等兩種情況，而等于具有傳遞性，相等就可以放入同一個集合中用樹結構存儲，判斷不等是否成立就可以看兩者是否處于同一集合中，若在同一集合說明兩者是相等的，此時不等一定不成立，直接返回false。所有情況都通過就返回true

數據范圍圖示：

注意：我們看到數據值的范圍是可以到達1e9的，但是我們的fa數組無法開辟那么多空間，而數據個數只有1e5的規模，所以我們可以通過離散化數據值來存儲進入fa數組，從而避免fa數組空間不足的情況出現

解題：

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 1e5 + 10;
int t,n;
//成組記錄，可以保留所有操作指令
struct node
{int i, j, e;
}a[N];
//離散化
int pos;
int disc[N * 2];
unordered_map<int, int> m;
//并查集
int fa[N * 2];
int find(int b)
{return fa[b] == b ? b : fa[b] = find(fa[b]);
}
void un(int b, int c)
{fa[find(b)] = find(c);
}
bool judge(int b, int c)
{return find(b) == find(c);
}
//解決函數
bool solve()
{//清空痕跡pos = 0;m.clear();//離散化操作cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].i >> a[i].j >> a[i].e;disc[++pos] = a[i].i;disc[++pos] = a[i].j;}sort(disc + 1, disc + 1 + pos);//升序排序int num = 0;for (int i = 1; i <= pos; i++){if (m.count(disc[i])) continue;//去重num++;m[disc[i]] = num;}//并查集操作//初始化for (int i = 1; i <= pos; i++){fa[i] = i;}for (int i = 1; i <= n; i++){if (a[i].e == 1)//合并{un(m[a[i].i], m[a[i].j]);}}for (int i = 1; i <= n; i++){//檢查判斷if (a[i].e == 0 && judge(m[a[i].i], m[a[i].j])){return false;}}return true;
}
int main()
{cin >> t;while (t--){if (solve()) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

注意：

1、由于我們的等式不等式有多組，所以我們使用結構體數組記錄數據，且這樣記錄還會將等式/不等式兩邊的對象和符號綁定起來，方便將數據離散化后可以直接知道哪些數之間有什么關系

2、由于需要判斷多組，所以我們需要將前面的殘留數據清除，disc直接用數據覆蓋即可，pos變量和m哈希表需要手動清除數據，fa則每次都進行初始化無需特殊處理。

3.在進行等式和不等式的并查集處理的時候不能放在一起只掃描一次，因為題目中的等于和不等于不一定是連續的，也就是說等于和不等于是摻雜在一起的，若一輪處理會導致判誤

舉例

? x1 = x2

? ?x2 ≠ x3

? ? ?x2 = x3

如果我們按順序合在一起掃描等式和不等式，那么在第二條地方不會返回false，因為x2和x3此時可以不等，且進入第三條我們也只是將集合合并，并未涉及判斷，最后會返回true

但是實際上等式是不成立的，所以我們應該先掃描一次所有等式，然后再掃描所有不等式進行判斷

錯誤代碼：

P1955 [NOI2015] 程序自動分析 - 洛谷