[NOI2015] 程序自动分析（并查集）

本文主要是介绍[NOI2015] 程序自动分析（并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题解

最后的结果与约束条件的顺序无关，可以先考虑相等条件，再考虑不等条件。由于题目中i和j的数据范围较大，需要用到离散化。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>using namespace std;const int N = 200010;int n, m;
int p[N];
unordered_map<int, int> S;struct Query
{int x, y, e;
} query[N];int get(int x)
{if (S.count(x) == 0) S[x] = ++n;return S[x];
}int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{int T;scanf("%d", &T);while (T--){n = 0;S.clear();scanf("%d", &m);for (int i = 0; i < m; i++){int x, y, e;scanf("%d%d%d", &x, &y, &e);query[i] = {get(x), get(y), e};}for (int i = 1; i <= n; i++) p[i] = i;// 合并所有相等约束条件for (int i = 0; i < m; i++)if (query[i].e == 1){int pa = find(query[i].x), pb = find(query[i].y);p[pa] = pb;}// 检查所有不等条件bool has_conflict = false;for (int i = 0; i < m; i++)if (query[i].e == 0){int pa = find(query[i].x), pb = find(query[i].y);if (pa == pb){has_conflict = true;break;}}if (has_conflict) puts("NO");else puts("YES");}return 0;
}

参考资料

1. AcWing算法提高课

这篇关于[NOI2015] 程序自动分析（并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---