题目大意
给定若干个相等约束、不相等约束,问是否存在矛盾
解题思路
并查集维护具有传递性的关系(本质是并查集在一张无向图中维护节点之间的连通性)。相等关系具有传递性,因此先保存下所有询问再离线处理。先处理所有的相等关系,再根据不相等关系寻找矛盾。
具体代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct query
{
int a, b, e;
};
query q[N];
int n, tt;
int p[N * 2];
map<int, int> S;
int get(int x) //离散化的一种简单写法
{
if (S.count(x) == 0)
S[x] = ++tt;
return S[x];
}
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
S.clear();
tt = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
int x, y, e;
cin >> x >> y >> e;
q[i] = {get(x), get(y), e};
}
for (int i = 0; i <= tt; i++)
p[i] = i;
for (int i = 0; i < n; i++) //先处理相等关系
{
if (q[i].e)
p[find(q[i].a)] = find(q[i].b);
}
bool has_conflict = false;
for (int i = 0; i < n; i++) //再处理不相等关系
{
if (!q[i].e)
{
if (find(q[i].a) == find(q[i].b)) //发现矛盾
{
has_conflict = true;
break;
}
}
}
if (has_conflict)
cout << "NO\n";
else
cout << "YES\n";
}
return 0;
}