「并查集」程序自动分析

程序自动分析

原题链接：程序自动分析

题目大意

给你很多逻辑关系，判断是否有冲突

题目题解

先将两个逻辑分开来看，前一个逻辑存在那么后一个逻辑一定不存在，如果存在那么答案就错误了，可以用并查集维护，详细见代码

//#define fre yes

#include <cstdio>
#include <iostream>
#include <algorithm>

const int N = 1000005;
struct message {
    int x, y, e;
} arr[N];
int ele[N << 1];

namespace Union {
    int par[N << 1];
    inline void init(int n) {
        for (int i = 1; i <= n; i++) {
            par[i] = i;
        }
    }

    inline int find(int x) {
        if(par[x] == x) return par[x];
        else return par[x] = find(par[x]);
    }

    inline void unite(int x, int y) {
        int a = find(x);
        int b = find(y);
        if(a == b) return ;

        par[a] = b;
    }

    inline bool same(int x, int y) {
        return find(x) == find(y);
    }
}

int n, m;
inline void discrete() {
    std::sort(ele + 1, ele + 1 + n * 2);
    m = std::unique(ele + 1, ele + 1 + 2 * n) - ele - 1;
}

inline int ask(int x) {
    return std::lower_bound(ele + 1, ele + 1 + m, x) - ele;
}

int main() {
    static int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d %d %d", &arr[i].x, &arr[i].y, &arr[i].e);
            ele[i] = arr[i].x; ele[i + n] = arr[i].y;
        } discrete();
        Union::init(m);
        for (int i = 1; i <= n; i++) {
            if(arr[i].e == 1) {
                Union::unite(ask(arr[i].x), ask(arr[i].y));
            }
        }

        bool flag = true;
        for (int i = 1; i <= n; i++) {
            if(arr[i].e == 0) {
                flag = flag && !Union::same(ask(arr[i].x), ask(arr[i].y));
            }
        }

        if(flag) puts("YES");
        else puts("NO");
    } return 0;
}