上鏈接：P1955 [NOI2015] 程序自動分析 - 洛谷 | 計算機科學(xué)教育新生態(tài) (luogu.com.cn)https://www.luogu.com.cn/problem/P1955

上題干：

首先給你一個整數(shù)t，代表t次操作。

每一次操作包含以下內(nèi)容：

1.給你一個整數(shù)n，讓你執(zhí)行n次條件

接下來n行，每行給你3個整數(shù)i，j，k，

例如 1 2?1

或? 1 2 0

(前面兩個數(shù)代表下標(biāo)，第三個整數(shù)k代表條件，如果它是1?,則代表?x1 = x2，如果它是0，代表x1！=x2）?

然后我們每一次操作需要輸出yes 或 no 來表示這n個條件是否全部成立。

（假如給出這樣的數(shù)據(jù)：

? ? n=4

? ? 1 2 1

? ? 2 3 1

? ? 1 4 1

? ? 3 4 0

? ? 第一個條件到第四個條件分別是 x1=x2，x2=x3，x1=x4 ，x3！=x4

由于前面三個條件我們可以得知? x1=x2=x3=x4? ?所以與x3！=x4矛盾，輸出no）

數(shù)據(jù) n<=1e6, i,j<=1e9

很顯然，這道題的條件和數(shù)據(jù)范圍告訴我們：需要用到并查集+（離散化 or hash表）

第一，并差集的特點就是能將不同的集合連接到一起，然后便于我們查詢某兩個元素是否為同一集合。

第二，這道題的數(shù)據(jù)范圍太大了，i能達到ie9，所以我們直接用并查集的話，毫無疑問，數(shù)組裝不下。所以我們可以用離散化來大大縮小數(shù)據(jù)范圍，除此之外呢，我們還可以用hash表來處理這樣的大數(shù)據(jù)，使得每一個大數(shù)據(jù)都有一個特別的標(biāo)記與之對應(yīng)。

這兩種方法都滿足我們的需求，這里主要用離散化來實現(xiàn)代碼。

還記得離散化的具體步驟嗎？

記錄散點，排序，去重，二分查找

并查集的具體步驟呢？

初始化集合，建立查詢函數(shù)，合并函數(shù)。

所以我們的思路是這樣的：

1，先將每一次的散點都存入一個數(shù)組b中

2，對這個數(shù)組b進行排序

3，對這個數(shù)組進行去重（可以選擇重新建立一個數(shù)組c來存放去重后的數(shù)據(jù)，也可以直接用unique函數(shù)。）

4，二分查找每一對散點的相對位置。

5，初始化并查集

6，如果第三個數(shù)字k=1，我們就利用并查集來合并兩個集合。

7，如果第三個數(shù)字k=0，我們就查詢兩個數(shù)是否為同一集合，如果是同一集合，那么我們有

上代碼：

const int MAXN = 1e6 + 10;
struct st {int x, y, z;
};
st a[MAXN];//三組輸入數(shù)據(jù)存放之處
int b[2 * MAXN];// 存入散點
int c[2 * MAXN];//排序數(shù)組
int fa[2 * MAXN];//并查集
int btop, ctop;int find1(int x)
{if (x == fa[x])return fa[x];return fa[x] = find1(fa[x]);
}
void join1(int c1, int c2)
{int f1 = find1(c1), f2 = find1(c2);if (f1 != f2)fa[f1] = f2;
}
int main()
{int t;cin >> t;while (t--){btop = 0;ctop = 0;int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].x >> a[i].y >> a[i].z;b[++btop] = a[i].x;b[++btop] = a[i].y;}sort(b + 1, b + 1 + btop);for (int i = 1; i <= btop; i++)if (i == 1 or b[i] != b[i - 1])c[++ctop] = b[i];for (int i = 1; i <= n; i++){a[i].x = lower_bound(c + 1, c + 1 + ctop, a[i].x) - c;a[i].y = lower_bound(c + 1, c + 1 + ctop, a[i].y) - c;}for (int i = 1; i <= ctop; i++){fa[i] = i;}for (int i = 1; i <= n; i++){if(a[i].z)join1(a[i].x, a[i].y);}bool fk = 1;for (int i = 1; i <= n; i++){if (a[i].z==0){if (find1(a[i].x) == find1(a[i].y))fk = 0;}}if (fk == 0)cout << "NO" << endl;else cout << "YES" << endl;}
}