NOI2015 程序自动分析

题解

分析

NOI 签到题
中途判断是错误的，比如首先读入 a != b,此时是不会判断出错的，然后读入a == b,此时也是不会判断出错的，那么程序就是错误的。

解

hash(用map水过) + 并查集
首先将所有的相等加入并查集，记录所有的不等，最后将不等统一判断即可

时间复杂度

并查集的时间复杂度可以忽略
logn为map的时间复杂度

Code

#include <bits/stdc++.h>
const int N = 1e5 + 10;
#define LL long long
int Ty, n;
std:: map <int, int> Map;
int fa[N << 1], Ask1[N], Ask2[N];
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
int Get_fa(int x) {
    return fa[x] == x ? x : fa[x] = Get_fa(fa[x]);
}
int main() {
    Ty = read();
    for(; Ty; Ty --) {
        Map.clear();
        n = read();
        int js(0), tot(0);
        for(int i = 1; i <= N * 2 - 10; i ++) fa[i] = i;
        for(int i = 1; i <= n; i ++) {
            int a = read(), b = read(), opt = read();
            if(Map[a]) a = Map[a]; else Map[a] = ++ js, a = js;
            if(Map[b]) b = Map[b]; else Map[b] = ++ js, b = js;
            if(opt == 1) {
                int fa_a = Get_fa(a), fa_b = Get_fa(b);
                fa[fa_a] = fa_b;
            } else {
                Ask1[++ tot] = a;
                Ask2[tot] = b; 
            }
        }
        bool flag = 1;
        for(int i = 1; i <= tot; i ++) {
            int fa_1 = Get_fa(Ask1[i]), fa_2 = Get_fa(Ask2[i]);
            if(fa_1 == fa_2) flag = 0;
        }
        if(!flag) puts("NO");
        else puts("YES");
    }
    return 0;
}