AcWing 237. 程序自动分析
题目类型
- 离散化
- 并查集
题目链接
思路
此题是NOI的一道题,掌握的话确实不难,而且感觉这题出的非常好,是并查集的经典题
- 由于该题数据是1e9 强行开1e9会TLE或者MLE,实际上用到最多只有只有2e5,所以使用离散化(这里不需要排序关系,使用哈希表)
- 所有等式相当于并查集合并,所有不等式相当于并查集查询
- 所以处理所有 = 等式
- 再查询所有 ≠ 等式,如果出现两个数在不同集合,说明存在冲突
AC代码
// 题目数据是1e9 可以用离散化缩小到2e6 (最关键在这步,否则会TLE)
// 将相等的式子 合并方式
// 将不等的式子 查询方式
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 2e6 + 10;
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);
if (pa != pb) 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) printf("NO\n");
else printf("YES\n");
}
return 0;
}