思路
处理的顺序:
先处理这些相等的,他们在同一个集合里面,最好处理;
再处理这些不相等的,只要判断是不是已经在同一个集合里面就可以了。
离散化
并查集初始化:每个节点初始化为本身的集合,只有自己一个元素;随着合并的进行,多个元素逐渐merge
知道题目中数据是非连续的,所以用离散化处理,由于不需要保序,所以只需要用hash,将成立后的值进行并查集的init。
代码
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 2000010;
int n, m;
int p[N];
unordered_map<int, int> mp;
struct Query
{
int x, y, e;
}q[N];
int get(int x)
{
if (mp.count(x) == 0) mp[x] = ++n;
return mp[x];
}
int find(int x)
{
if (p[x] == x) return x;
else return p[x] = find(p[x]);
}
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> m;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
q[i] = {get(a), get(b), c};
}
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 0; i < m; i++)
{
if (q[i].e == 1)
{
int px = find(q[i].x), py = find(q[i].y);
p[px] = py;
}
}
bool has_conflict = false;
for (int i = 0; i < m; i++)
{
if (q[i].e == 0)
{
int px = find(q[i].x), py = find(q[i].y);
if (px == py)
{
has_conflict = true;
break;
}
}
}
if (has_conflict) puts("NO");
else puts("YES");
mp.clear();
}
return 0;
}