M_sea

洛谷1955 [NOI2015]程序自动分析
Luogu算法如果$a=b$,$b=c$,那么$a=c$。考虑用并查集维护相等关系,在一个集合内则相等,否则则不等...
扫描右侧二维码阅读全文
14
2018/08

洛谷1955 [NOI2015]程序自动分析

Luogu

算法

如果$a=b$,$b=c$,那么$a=c$。

考虑用并查集维护相等关系,在一个集合内则相等,否则则不等。

对于一组数据中的相等关系,先把它们合并。

然后处理所有不等的关系。若对于一组$a\neq b$,$a$、$b$在一个集合内,那么不合法。

注意到本题数据范围到了$10^9$,但个数却只有$10^5$,那么考虑离散化。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int root[1000010];

inline void init(int n) {
    for (re int i=1;i<=n;i++) root[i]=i;
}

inline int find(int x) {
    if (root[x]!=x) root[x]=find(root[x]);
    return root[x];
}

inline void merge(int a,int b) {
    a=find(a),b=find(b);
    if (a!=b) root[a]=b;
}

int tmp[2000010];
int op[1000010][3];

int main() {
    int T=read();
    while (T--) {
        int n=read(),tmps=0;
        for (re int i=1;i<=n;i++) {
            op[i][1]=read(),op[i][2]=read(),op[i][0]=read();
            tmp[++tmps]=op[i][1]; tmp[++tmps]=op[i][2];
        }
        sort(tmp+1,tmp+tmps+1);
        int m=unique(tmp+1,tmp+tmps+1)-tmp-1;
        for (re int i=1;i<=n;i++) {
            op[i][1]=lower_bound(tmp+1,tmp+m+1,op[i][1])-tmp;
            op[i][2]=lower_bound(tmp+1,tmp+m+1,op[i][2])-tmp;
        }
        init(m);
        for (re int i=1;i<=n;i++)
            if (op[i][0]==1) merge(op[i][1],op[i][2]);
        bool f=1;
        for (re int i=1;i<=n;i++)
            if (op[i][0]==0&&find(op[i][1])==find(op[i][2])) {
                puts("NO"); f=0; break;
            }
        if (f) puts("YES");
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 48 PM

发表评论