[51nod1515]明辨是非

Description

给\(n\)组操作,每组操作形式为\(x\;y\;p\).

当\(p=1\)时,如果第\(x\)变量和第\(y\)个变量可以相等,则输出\(YES\),并限制他们相等;否则输出\(NO\),并忽略此次操作.

当\(p=0\)时,如果第\(x\)变量和第\(y\)个变量可以不相等,则输出\(YES\),并限制他们不相等;否则输出\(NO\),并忽略此次操作.

Input

输入一个数\(n\)表示操作的次数.接下来\(n\)行每行三个数\(x,y,p\).

Output

对于\(n\)行操作，分别输出\(n\)行\(YES\)或者\(NO\).

Sample Input

3
1 2 1
1 3 1
2 3 0

Sample Output

YES
YES
NO

HINT

\(n\;\leq\;10^5,x,y\;\leq\;10^8,p=0\;or\;1\).

Solution

离散化所有的变量.

可以用并查集维护相等的关系,\(set\)维护不等的关系.

当\(p=1\)时,如果\(x,y\)都不在对方的\(set\)中,则可行,按\(set\)大小合并它们的父亲和\(set\);

当\(p=0\)时,如果\(f[x]\not=f[y]\),把\(f[x],f[y]\)分别插入对方的\(set\)中.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 200005
using namespace std;
int a[N],f[N],x[N],y[N],p[N],n,m;
set s[N];
set::iterator l;
inline int gf(int k){
    if(f[k]==k) return k;
    return f[k]=gf(f[k]);
}
inline int search(int k){
    int l=1,r=m,mid;
    while(l>1;
        if(a[mid]s[k].size()) swap(j,k);
                f[j]=k;
                for(l=s[j].begin();l!=s[j].end();++l){
                    q=gf(*l);
                    s[*l].erase(j);
                    s[q].insert(k);
                    s[k].insert(q);
                }
                s[j].clear();
            }
        }
    }
}
int main(){
    freopen("judge.in","r",stdin);
    freopen("judge.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}