题目链接：https://www.luogu.com.cn/problem/P1955

 题目：

题目描述

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设 x_1,x_2,x_3,\cdotsx1​,x2​,x3​,⋯ 代表程序中出现的变量，给定 nn 个形如 x_i=x_jxi​=xj​或 x_i\neq x_jxi​=xj​ 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1x1​=x2​,x2​=x3​,x3​=x4​,x4​=x1​，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

输入格式

输入的第一行包含一个正整数 tt，表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题，包含若干行：

第一行包含一个正整数 nn，表示该问题中需要被满足的约束条件个数。接下来 nn 行，每行包括三个整数 i,j,ei,j,e，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 e=1e=1，则该约束条件为 x_i=x_jxi​=xj​。若e=0e=0，则该约束条件为 x_i\neq x_jxi​=xj​。

输出格式

输出包括 tt 行。

输出文件的第 kk 行输出一个字符串 YES 或者 NO（字母全部大写），YES 表示输入中的第 kk 个问题判定为可以被满足，NO 表示不可被满足。

输入输出样例

输入 #1复制

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

输出 #1复制

NO
YES

输入 #2复制

2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

输出 #2复制

YES
NO

说明/提示

【样例解释1】

在第一个问题中，约束条件为：x_1=x_2,x_1\neq x_2x1​=x2​,x1​=x2​。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：x_1=x_2,x_1 = x_2x1​=x2​,x1​=x2​。这两个约束条件是等价的，可以被同时满足。

【样例说明2】

在第一个问题中，约束条件有三个：x_1=x_2,x_2= x_3,x_3=x_1x1​=x2​,x2​=x3​,x3​=x1​。只需赋值使得 x_1=x_2=x_3x1​=x2​=x3​，即可同时满足所有的约束条件。

在第二个问题中，约束条件有四个：x_1=x_2,x_2= x_3,x_3=x_4,x_4\neq x_1x1​=x2​,x2​=x3​,x3​=x4​,x4​=x1​。由前三个约束条件可以推出 x_1=x_2=x_3=x_4x1​=x2​=x3​=x4​，然而最后一个约束条件却要求 x_1\neq x_4x1​=x4​，因此不可被满足。

【数据范围】

注：实际上 n\le 10^6n≤106 。

 思路：

1.离散化

1.首先，此题的数据范围i,j很大，1e9的范围， 而n的范围 <= 1e6,每个n对应两个点，所以总共使用到的数据不会超过 2e6。而此种情况，便可以想到需要使用离散化。 

2.而离散化的时候，有两种离散化的情况，

（1）离散化后需要保序，也就是需要原先x < y, 离散化后 get(x) < get(y),

这种方式就是之前学过的，先sort 。  然后 e.erase(unique( e.begin(),e.end() ), e.end() ).

(2)离散化后不需要保序， 则可以直接使用哈希 unordered_map<int,int> q. 

判断这个值x是否再哈希中，q.count(x),  如果再，直接return q[x];

如果不在 q[x] = ++idx;

return q[x];

 2.并查集：

离散化了x1,x2后，就需要判断是否所给条件矛盾。

而我们可以发现，

先给出的条件得到，a 与 b 相等后。 再给出 a 与 b 不相等。矛盾

先给出的条件得到，a 与 b 不相等后， 再给出a 与 b 相等， 也矛盾

也就是矛盾的情况，与给出的条件的顺序无关。

那么我们就可以先完成所有给出的条件中，相等的情况。 因为 得到a,b相等之后 再给出a,b不相等则矛盾容易判断。

而a,b相等直接让它们再同一集合中， a,b不相等则不在同一集合中。 

那么矛盾的情况就是a,b已经再同一集合中了，你现在却说要a,b不在同一集合中。

这就用到了并查集的，合并 和 查询 操作。

 代码实现：

# include <iostream>
# include <unordered_map>
using namespace std;

const int N = 2e6 + 10;

int p[N];

int n;

unordered_map <int,int> h;
int idx = 0;

struct edg
{
    int a,b,e;
} edg[N];

int get(int x)
{
    if(!h.count(x))
    {
        h[x] = ++idx;
    }
    return h[x];
}

int find2(int x)
{
    if(p[x] != x)
    {
        p[x] = find2(p[x]);
    }
    return p[x];
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        
        h.clear();
        idx = 0;  // 此两行清空上一次测试数据的影响。
        
        for(int i = 1 ; i <= n ; i++)
        {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            edg[i] = {get(x),get(y),z};
        }

        for(int i = 1 ; i <= 2 * n ; i++)
        {
            p[i] = i;
        }

        for(int i = 1; i <= n ; i++)
        {
            if(edg[i].e == 1)
            {
                int temp1 = find2(edg[i].a);
                int temp2 = find2(edg[i].b);
                p[temp1] = temp2;
            }
        }
        bool flag = true;
        for(int i = 1 ; i <= n ; i++)
        {
            if(edg[i].e == 0)
            {
                int temp1 = find2(edg[i].a);
                int temp2 = find2(edg[i].b);
                if(temp1 == temp2)
                {
                    flag = false;
                    break;
                }
            }
        }
        if(flag)
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
    }
    return 0;
}