【LOJ】#2129. 「NOI2015」程序自动分析

题解

开始是想两个并查集的

和A相等，和A不相等

如果AB相等就连

A 相等，B相等

B不相等 A不相等

如果AB不相等就连

A不相等，B相等

B相等，A不相等

但是显然不对，因为和A不相等的不一定和B相等

所以我就gg了，后来发现只要把所有相等的先连上然后看看不相等的有没有在同一集合就行

老年选手连并查集都写跪= =丢人= =

代码

#include <bits/stdc++.h>

//#define ivorysi

#define enter putchar('\n')

#define space putchar(' ')

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define mo 974711

#define MAXN 1000005

#define pii pair<int,int>

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int T;

int N;

int fa[MAXN * 4];

int X[MAXN],Y[MAXN],e[MAXN];

int num[MAXN * 2],tot;

int getfa(int x) {

    return fa[x] == x ? x : fa[x] = getfa(fa[x]);

}

void Solve() {

    read(N);

    tot = 0;

    for(int i = 1 ; i <= N ; ++i) {

	read(X[i]);read(Y[i]);read(e[i]);

	num[++tot] = X[i];num[++tot] = Y[i];

    }

    sort(num + 1,num + tot + 1);

    tot = unique(num + 1,num + tot + 1) - num - 1;

    for(int i = 1 ; i <= tot ; ++i) fa[i] = i;

    for(int i = 1 ; i <= N ; ++i) {

	X[i] = lower_bound(num + 1,num + tot + 1,X[i]) - num;

	Y[i] = lower_bound(num + 1,num + tot + 1,Y[i]) - num;

	if(e[i] == 1) {

	    fa[getfa(X[i])] = getfa(Y[i]);

	}

    }

    for(int i = 1 ; i <= N ; ++i) {

	if(e[i] == 0) {

	    if(getfa(X[i]) == getfa(Y[i])) {

		puts("NO");return;

	    }

	}

    }

    puts("YES");

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    read(T);

    while(T--) {

	Solve();

    }

    return 0;

}