《洛谷深入浅出进阶篇》P1995 程序自动分析——并查集，离散化
上链接：P1955 [NOI2015] 程序自动分析 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
https://www.luogu.com.cn/problem/P1955
上题干：
首先给你一个整数t，代表t次操作。
每一次操作包含以下内容：
1.给你一个整数n，让你执行n次条件
接下来n行，每行给你3个整数i，j，k，
例如 1 2 1
或 1 2 0
(前面两个数代表下标，第三个整数k代表条件，如果它是1 ,则代表 x1 = x2，如果它是0，代表x1！=x2）
然后我们每一次操作需要输出yes 或 no 来表示这n个条件是否全部成立。
（假如给出这样的数据：
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）
数据 n<=1e6, i,j<=1e9
很显然，这道题的条件和数据范围告诉我们：需要用到并查集+（离散化 or hash表）
第一，并差集的特点就是能将不同的集合连接到一起，然后便于我们查询某两个元素是否为同一集合。
第二，这道题的数据范围太大了，i能达到ie9，所以我们直接用并查集的话，毫无疑问，数组装不下。所以我们可以用离散化来大大缩小数据范围，除此之外呢，我们还可以用hash表来处理这样的大数据，使得每一个大数据都有一个特别的标记与之对应。
这两种方法都满足我们的需求，这里主要用离散化来实现代码。
还记得离散化的具体步骤吗？
记录散点，排序，去重，二分查找
并查集的具体步骤呢？
初始化集合，建立查询函数，合并函数。
所以我们的思路是这样的：
1，先将每一次的散点都存入一个数组b中
2，对这个数组b进行排序
3，对这个数组进行去重（可以选择重新建立一个数组c来存放去重后的数据，也可以直接用unique函数。）
4，二分查找每一对散点的相对位置。
5，初始化并查集
6，如果第三个数字k=1，我们就利用并查集来合并两个集合。
7，如果第三个数字k=0，我们就查询两个数是否为同一集合，如果是同一集合，那么我们有
上代码：
const int MAXN = 1e6 + 10;
struct st {
int x, y, z;
};
st a[MAXN];//三组输入数据存放之处
int b[2 * MAXN];// 存入散点
int c[2 * MAXN];//排序数组
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;
}
}