《洛谷深入浅出进阶篇》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;}
}