算法提高课汇总

算法思路

考虑相等关系的传递性, 如果$x_i = x_j$, 可视为将它们加入同一集合中, 且集合
中所有元素均满足相等关系.

由于约束条件的顺序对问题的结果没有影响, 我们可以先考虑相等关系, 将相等
元素加入同一集合中, 接着考虑约束关系$x_i\not= x_j$, 如果$x_i$与$x_j$在同一集合中,
则约束条件不满足, 否则由于$x$值可任意赋予, 所以当前约束关系满足.

具体实现

实现时由于$x$下标范围在$10^9$, 而一次输入所有下标值只有$2\times 10^5$(有用的下标),
所以需要对下标做离散化处理.

实现代码

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 2e5 + 10;

int n, m;
int p[N];
unordered_map<int, int> mp;
struct Query
{
    int x, y, e;
}query[N]; //先保存查询

int get(int x)
{//非保序离散化
    if ( mp.count(x) ==0 )  mp[x] = ++ n;
    return mp[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;
        mp.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 flag = 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 )
                {
                    flag = true;
                    break;
                }
            }
        if ( flag ) puts("NO");
        else    puts("YES");
    }

    return 0;
}