【题解】LOJ 2129 「NOI2015」程序自动分析

Problem

给定 $n$ 个形如 $x_i=x_j$ 或者 $x_i\neq x_j$ 的关系,问是否存在一种方案使得所有关系均成立

Thought

显然是个并查集

把所有条件离线下来,先搞相等的,然后判断不相等关系是否成立即可

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

const int N = 1000010;

int n, fa[N << 1], num[N << 1];
unordered_map <int, int> mp;
int tot;

int u[N], v[N], w[N];

int find(int x) {return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);}

void merge(int a, int b) {
    a = find(a); b = find(b);
    if(num[a] > num[b]) swap(a, b);
    fa[a] = b;
    num[n] += num[a];
}

void work() {
    mp.clear(); tot = 0;
    n = read();
    for(int i = 1; i <= n; ++ i) {
        u[i] = read(); v[i] = read(); w[i] = read();
        if(!mp[u[i]]) mp[u[i]] = ++ tot;
        u[i] = mp[u[i]];
        if(!mp[v[i]]) mp[v[i]] = ++ tot;
        v[i] = mp[v[i]];
    }
    for(int i = 1; i <= tot; ++ i) {
        fa[i] = i; num[i] = 1;
    }
    for(int i = 1; i <= n; ++ i)
        if(w[i] == 1)
            merge(u[i], v[i]);
    for(int i = 1; i <= n; ++ i)
        if(w[i] == 0)
            if(find(u[i]) == find(v[i])) {
                puts("NO"); return;
            }
    puts("YES");
    return;
}

int main() {
    int t = read();
    while(t --)
        work();
    return 0;
} 
Comments

添加新评论